Cho phương trình bậc ba ~ax^3+bx^2+cx+d=0~ với ~a,b,c,d~ là các số nguyên có trị tuyệt đối không vượt quá ~10^4~ và ~a \neq 0, \, d \neq 0.~ Yêu cầu đặt ra là in ra các nghiệm nguyên (nếu có) của phương trình này.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ cho biết số lượng phương trình cần xét, trong đó ~1 \le n \le 10^5~. Với mỗi dòng tiếp theo sẽ gồm ~4~ số ~a,b,c,d~ thỏa mãn ràng buộc như đề bài.

Output

Với mỗi phương trình, nếu nó không có nghiệm nguyên thì in ra NO; nếu có nghiệm nguyên thì in ra các nghiệm đó, theo thứ tự từ nhỏ đến lớn.

Sample input 1

1
1 1 1 2

Sample output 1

NO

Sample input 2

2
1 1 1 1
1 -6 11 -6

Sample output 2

-1
1 2 3

Giải thích phương trình ~x^3+x^2+x+2=0~ không có nghiệm nguyên, còn phương trình ~x^3+x^2+x+1=(x+1)(x^2+1)=0~ có nghiệm nguyên duy nhất là ~x=-1~, còn phương trình ~x^3-6x^2+11x-6=(x-1)(x-2)(x-3)=0~ có ba nghiệm ~x=1,2,3~.

Subtasks:

• Có 50% số test ứng với ~n \le 10~.
• Có 50% số test không có ràng buộc gì thêm.

Nhận thấy các con của mình rất chăm học thuật toán nên bố Tài SC (super cute) đã ra cho chúng một bài toán ngây thơ như sau: cho ~q~ số nguyên dương (không nhất thiết phân biệt), hãy tính tổng ước của từng số. Các con cảm thấy rất giận dỗi vì lại ra một bài căn bản như thế, cho đến khi chúng đọc được kỹ các subtask, hãy làm thử bài toán này của bố Tài nhé.

Input

Dòng đầu tiên là số nguyên dương ~q~.

Dòng tiếp theo là ~q~ số nguyên dương ~a_1, a_2, ..., a_q.~

Output

In ra ~q~ số là đáp số của bài toán.

Sample input

4
2 4 10 9

Sample output

3 7 18 13

Subtasks

• Subtask 1 (15% số điểm): ~q ≤ 10^4; a_i ≤ 10^3~ với ~(1 ≤ i ≤ q)~
• Subtask 2 (25% số điểm): ~q ≤ 10^5; a_i ≤ 10^5~ với ~(1 ≤ i ≤ q)~
• Subtask 3 (35% số điểm): ~q ≤ 10^5; a_i ≤ 10^6~ với ~(1 ≤ i ≤ q)~
• Subtask 4 (25% số điểm): ~q ≤ 10^6; a_i ≤ 10^{12}~ và ~a_{i+1} = a_i + 1~ với ~1 ≤ i <q.~</li>

Anh Phú sau khi giải nghệ ở kỳ thi chuyên Tin thì đã về nuôi gà và trồng thêm hoa. Phú rất thích trồng hoa ly ly và anh xếp ~N~ khóm hoa của mình, được đánh số từ 1 đến ~N~, thành một hàng ngang để đo chiều cao của chúng, khóm hoa thứ ~i~ có chiều cao là ~h_i~. Sau đó anh ta muốn chụp ảnh một số dãy con gồm những khóm hoa liên tiếp nhau để mang đến dự thi cuộc thi nhiếp ảnh tại một hội chợ hoa do thầy Luna tổ chức. Cuộc thi này có một quy định là chỉ những bức ảnh có trung vị chiều cao của những khóm hoa trong ảnh lớn hơn hoặc bằng ~K~ thì mới hợp lệ và được dự thi.

Chú ý: trung vị của một dãy số ~a_1,a_2,...,a_n~ có ~n~ sẽ được tính như sau: sắp xếp dãy tăng dần thì trung vị là ~a_{n/2+1}~ nếu ~n~ chẵn và là ~a_{(n+1)/2}~ nếu ~n~ lẻ.

Hỏi anh Phú có thể chụp được bao nhiêu bức ảnh hợp lệ?

Input

Dòng đầu tiên gồm số nguyên dương ~n, k~ với ~1 \le n \le 10^5~ và ~1 \le k \le 10^9.~

Dòng tiếp theo gồm các số nguyên dương cho biết chiều cao của khóm hoa, không vượt quá ~10^9.~

Output

Số khóm hoa thỏa mãn.

Sample input

4 6
10 5 6 2

Sample output

7

Giải thích: các dãy con sau đây thỏa mãn: ~(10), (6), (5, 6), (10, 5), (5, 6), (6, 2), (10, 5, 6), (10, 5, 6, 2).~

Subtasks

• Subtask 1 (30% số test): ~n \le 500~.
• Subtask 2 (70% số test): Không có ràng buộc gì thêm.

Thành phố Huế có ~n~ địa điểm du lịch và được đánh số từ ~1~ đến ~n~. Các địa điểm được nối với nhau bởi hệ thống giao thông gồm ~m~ tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp địa điểm, đảm bảo luôn có đường đi lại giữa hai địa điểm bất kì (trực tiếp hoặc đi qua một số địa điểm khác). Team ICPC năm nay của IUH đã lên kế hoạch tham quan các địa điểm du lịch, kết hợp với ăn uống các đặc sản của Huế. Team không mang theo tiền mặt mà dự định sẽ đi rút tiền tại các máy ATM, mỗi khi muốn đi ăn ở đâu đó. Có ~b~ địa điểm trong đó có đặt máy ATM để rút tiền và ~r~ địa điểm ăn uống. Yêu cầu đặt ra là từ một địa điểm ăn uống bất kỳ, hãy giúp team tính ra độ dài của tuyến đường ngắn nhất đến một máy ATM tùy nào nào đó trong ~b~ địa điểm.

Input

Dòng đầu tiên gồm 4 số ~n, m, b, r~ trong đó ~n~ là số địa điểm, ~m~ là số tuyến đường, ~b~ là số vị trí đặt máy ATM và ~r~ là số địa điểm ăn uống (~2 \le n \le 5 \times 10^5; 1 \le m \le 5 \times 10^5; 1 \le b, r \le n.~).

Dòng hai là STT của các vị trí rút tiền, các số phân biệt trong khoảng từ ~1~ đến ~n~.

Dòng ba là STT cả các vị trí ăn uống, các số phân biệt trong khoảng từ ~1~ đến ~n~.

Tiếp theo m dòng là đường đi 2 chiều giữa các địa điểm.

Output

In ra ~r~ số nguyên cho biết độ dài ngắn nhất từ một địa điểm ăn uống thứ ~i~ với ~1 \le i \le n~ đến một máy rút tiền nào đó.

Sample input

6 6 2 3
3 2
1 5 4
1 2
1 6
3 6
2 3
4 5
3 4

Sample output

1 2 1

Giải thích: ~1 \to 2~, ~5 \to 4 \to 3~, ~4 \to 3~.

Subtasks

• Subtask 1: (40% số test): ~2 \le n \le 2000; 1 \le m \le 2000.~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.