Do ở nhà nghỉ dịch quá lâu nên các bạn trong lớp ntkwan có vẻ đã quên hết mặt nhau. Vì vậy ntkwan quyết định tổ chức một buổi dạ hội với sự góp mặt của tất cả các thành viên trong lớp để chúc mừng năm mới và chuẩn bị tinh thần quay trở lại trường học.

Có tổng cộng ~N~ bạn tham gia dạ hội. Trong buổi dạ hội, mỗi bạn nam sẽ khiêu vũ với ~X~ bạn nữ khác nhau, và mỗi bạn nữ cũng sẽ khiêu vũ với ~Y~ bạn nam khác nhau. Tuy nhiên, do sơ suất, ntkwan đã làm mất tờ giấy ghi số bạn nam và số bạn nữ sẽ tham gia dạ hội.

Bạn hãy giúp ntkwan tính số bạn nam và số bạn nữ tham gia dạ hội nhé!

Input

• Dòng đầu chứa số test ~T~ (~1 \le T \le 10^4~).
• ~T~ dòng tiếp theo, dòng thứ ~i~ chứa dữ liệu của test case thứ ~i~, bao gồm: ~3~ số ~N, X, Y~ (~2 \le X, Y \le N \le 10^9~).

Output

• Ứng với mỗi test case, in ra hai số ~A~ và ~B~ thể hiện số lượng bạn nam và số lượng bạn nữ, nếu số lượng bạn nào chiếm ít hơn thì in đầu tiên và theo sau là số lượng bạn chiếm nhiều hơn.
• Biết rằng với mỗi input đảm bảo đều có đáp án nguyên dương.

Sample Input

2
10 2 3
126 80 40

Sample Output

4 6
42 84

Nhân ngày đầu năm mới, thầy giáo của Phát muốn tặng mỗi bạn một điểm số để chọn làm điểm bài kiểm tra 15 phút.

Lớp Phát có ~n~ bạn, được đánh số lần lượt từ ~1~ đến ~n~. Thầy giáo dự định cho điểm như sau:

• Đầu tiên thầy giáo chọn ~4~ số ~m, k, x, q~.

• Gọi điểm bạn thứ ~i~ là ~a_i~.

• ~a_i = x~ nếu ~i = 1~.

• Nếu ~i > 1~ thì ~a_i = (a_{i - 1} \times k) \bmod m~.

• Sau đó lại trừ điểm của tất cả các bạn ~q~ điểm.

Lưu ý điểm có thể âm. (điểm âm là do các bạn kém may mắn :))

Cụ thể hơn, điểm thầy giáo định cho ban đầu được tính bằng mã giả sau:

a[1] = x;
for i from 2 to n:
    a[i] = (a[i - 1] * k) mod m;
for i from 1 to n:
    a[i] = a[i] - q;

Lưu ý: mọi tính toán nên được thực hiện với số nguyên 64-bit.

Sau khi làm các bước như thế thì thầy giáo thấy điểm vẫn còn quá cao nên quyết định thử ~t~ trường hợp.

Mỗi trường hợp thầy chọn ~3~ số ~L, R, D~, điểm số của bạn thứ ~i~ sẽ bị trừ ~D~ nếu ~L \le i \le R~.

Thầy giáo muốn biết trong mỗi trường hợp đó thì số điểm lớn nhất của lớp là bao nhiêu. Bạn hãy giúp thầy giáo nhé!

Input

• Dòng đầu chứa năm số nguyên ~n,m,k,x,q~ ~(1 \le n \le 10^7, 1 \le m, k, x, q \le 10^9)~.
• Dòng thứ hai chứa số nguyên dương ~t~. ~(1 \le t \le 10^5)~
• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~L_i, R_i, D_i~ cho biết truy vấn thứ ~i~ ~(1 \le L_i \le R_i \le n, 0 \le D_i \le 10^9)~.

Output

• Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask 1 (30% số điểm): ~n \le 1000~
• Subtask 2 (30% số điểm): ~n \le 10^5~
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm

Sample Input

5 7 5 1 1
3
1 3 3
1 5 5
4 5 2

Sample Output

5
0
4

Note

• Dãy được sinh ra là ~a=[0, 4, 3, 5, 1 ]~.
• Trong truy vấn ~1~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[-3,1,0,5,1]~.
• Trong truy vấn ~2~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[-5,-1,-2,0,-4]~.
• Trong truy vấn ~3~, dãy ~a~ sau khi trừ điểm các bạn có số thứ tự trong đoạn ~[L,R]~ ~D~ điểm là ~a=[0,4,3,3,-1]~.

Có lẽ sau một thời gian rất dài chỉ ngồi coding, Lộkk cảm thấy thực sự căng thẳng và mệt mỏi. Vì vậy hôm nay Lộkk quyết định chọn ra một hoạt động mới giúp Lộkk cảm thấy thư giãn hơn. Lộkk ngồi đắn đo suy nghĩ. Các môn thể thao thì thực sự rất vui, nhưng mọi người cũng phải ở nhà hết rồi! Nếu chuyển qua chơi game, vậy cũng không khác nào ngồi coding với máy tính cả.

Lộkk quyết định chia sẻ những đắn đo này với Nhật, và Nhật gợi ý rằng: "Hay là làm vườn? Làm vườn tốt cho sức khỏe. Làm vườn ở ngoài trời, làn da tiếp xúc với ánh nắng có thể giúp có thể tăng cường Vitamin D. Làm vườn cũng giúp giảm huyết áp nè. Ngoài ra đây cũng là hoạt động nhẹ nhàng, giúp giảm căng thẳng rất hiệu quả!"

Lộkk thấy ý tưởng của Nhật quả là tuyệt vời, vì vậy Lộkk đã quyết định tạo ra một vườn hoa của riêng mình. Vườn hoa mà Lộkk định trồng có dạng một hình chữ nhật có kích thước ~n \times m~. Hình chữ nhất được chia thành các hàng và cột, với các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~m~ từ trái qua phải. Ô ở hàng thứ ~r~ và cột thứ ~c~ được thể hiện bởi cặp số ~(r, c)~.

Là người yêu thích toán học, nên Lộkk muốn khu vườn của mình cũng có tính chất đặc biệt. Lộkk chỉ trồng hoa vào các ô ~(r, c)~ nếu như ~r + c~ là số nguyên tố.

Cho kích thước khu vườn của Lộkk, hãy giúp Lộkk tìm xem Lộkk cần phải trồng bao nhiêu bông hoa trong khu vườn nhé!

Input

Gồm một dòng duy nhất chứa hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^6)~ là kích thước khu vườn của Lộkk.

Output

In ra một số nguyên duy nhất là số bông hoa mà Lộkk cần trồng.

Sample Input 1

5 5

Sample Output 1

11

Sample Input 2

10 7

Sample Output 2

26

Note

Dưới đây là hình minh họa cho hai test ví dụ.

Sau thời gian dài không đến trường thì cây cối ở trường iostream không ai chăm sóc đã trở nên yếu ớt và héo dần.

Nhà trường muốn xây dựng ngôi trường xanh nên đã tổ chức cuộc thi trồng cây. iostream rất hào hứng và đăng ký tham gia ngay lập tức. Thế nhưng khi nghe chi tiết về cuộc thi thì bất lực vì yêu cầu quá rắc rối và phức tạp.

Trường yêu cầu mỗi thí sinh phải trồng được một dãy ~n~ cây với chiều cao lần lượt là ~a_1, a_2, \ldots, a_n~ và phải thỏa mãn các yêu cầu của cuộc thi:

• Chiều cao của mỗi cây phải có dạng ~p^k~ với ~p~ là số nguyên tố bất kỳ và ~k~ là số nguyên không âm.

• Tổng giá trị của tất cả các subsequence của dãy phải đúng bằng ~x~.

Một subsequence của một dãy cây có thể thể thu được bằng cách bỏ đi trong dãy cây đó một số cây bất kì (các cây được bỏ đi không nhất thiết phải liên tiếp). Giá trị một subsequence được tính bằng chiều cao của cây lớn nhất nằm trong subsequence đó, hoặc bằng ~0~ nếu subsequence rỗng.

Bạn hãy giúp iostream tìm ra chiều cao của các cây cần trồng nhé!

Input

• Dòng đầu tiên bao gồm duy nhất một số nguyên ~t~ (~1 \le t \le 1000~) là số lượng số test case.

• Mỗi một test case được mô tả bởi duy nhất một dòng, mỗi dòng chứa duy nhất một số nguyên ~x~ (~1 \le x \le 10^{18})~.

Output

Với mỗi một test case, hãy in ra hai dòng.

• Dòng đầu tiên chứa số ~n~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~.

Output cần phải đảm bảo đúng yêu cầu của cuộc thi (trên thực tế, luôn tồn tại ít nhất 1 cách trồng cây thỏa mãn).

Sample Input 1

2
42
30

Sample Output 1

3
5 4 7
2
11 8

Sample Input 2

2
22
130

Sample Output 2

2
9 4
3
11 25 8

Notes

Ở test thứ nhất, test case đầu tiên, các subsequence của output và giá trị tương ứng của chúng được biểu diễn như bảng dưới đây

Hôm nay là ngày đầu Hiệp đến trường sau ~8~ tháng nghỉ ~30/4~. Hiệp ôm trong lòng tâm trạng vui vẻ, phấn khởi vì cuối cùng cậu cũng được gặp crush.

Thế nhưng niềm vui thì lại hay đi kèm với nỗi buồn. Crush của Hiệp là một người rất thích những câu đố. Lần này khi vừa bước vào lớp, Hiệp còn chưa được gặp mặt crush mà đã thấy một dãy số khó hiểu trên bảng.

Câu đố của crush là: Cho dãy ~N~ số nguyên ~p_1, p_2, \dots, p_n~ là một hoán vị của ~1, 2, \dots, N~. Bạn được thực hiện thao tác sau nhiều lần: chọn một dãy con (không nhất thiết liên tiếp) của ~p~ chứa không quá ~K~ phần tử và sắp xếp các phần tử trong dãy con đó tăng dần. Tuy nhiên, mỗi phần tử của ~p~ chỉ được chọn trong tối đa một thao tác. Tìm hoán vị có thứ tự từ điển nhỏ nhất có thể đạt được.

Hiệp rất muốn giải câu đố này để lấy le nhưng não Hiệp đang bị dừng mất mấy nhịp vì nụ cười tỏa nắng của crush. Bạn hãy giúp Hiệp nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le K \le N \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~p_1, p_2, \dots, p_N~ là một hoán vị của ~1, 2, \dots, N~.

Output

• In ra trên một dòng duy nhất ~N~ số nguyên dương là hoán vị có thứ tự từ điển nhỏ nhất có thể đạt được.

Subtask

• Subtask 1 (50% số điểm): ~N \le 3000~
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm

Sample Input 1

5 2
4 3 2 5 1

Sample Output 1

1 2 3 5 4

Sample Input 2

10 3
5 8 2 1 7 6 9 3 10 4

Sample Output 2

1 2 3 4 6 7 9 8 10 5

Note

Trong ví dụ thứ nhất, các thao tác là:

• Chọn dãy con chứa phần tử thứ nhất và phần tử thứ năm. Sau thao tác, ~p = [1, 3, 2, 5, 4]~.
• Chọn dãy con chứa phần tử thứ hai và phần tử thứ ba. Sau thao tác, ~p = [1, 2, 3, 5, 4]~.

Trong ví dụ thứ hai, các thao tác là:

• Chọn dãy con chứa các phần tử có chỉ số ~1~, ~4~ và ~10~. Sau thao tác, ~p = [1, 8, 2, 4, 7, 6, 9, 3, 10, 5]~.
• Chọn dãy con chứa các phần tử có chỉ số ~2~, ~3~ và ~8~. Sau thao tác, ~p = [1, 2, 3, 4, 7, 6, 9, 8, 10, 5]~.
• Chọn dãy con chứa các phần tử có chỉ số ~5~ và ~6~. Sau thao tác, ~p = [1, 2, 3, 4, 6, 7, 9, 8, 10, 5]~.

Trong thời gian rảnh rỗi ở nhà học online, Phát đã nghĩ ra một trò chơi để giải trí trong lúc "afk". Trò chơi gồm một bảng kích thước ~r \times c~, ô nằm ở hàng ~i~, cột ~j~ là ~(i, j)~. Ban đầu, mọi ô trên bảng đều bằng ~0~.

Phát cũng thiết kế thêm các nút bấm ở mỗi hàng sao cho khi bấm nút ở hàng ~i~ thì sẽ làm tăng tất cả các ô ở hàng ~i~ lên ~1~ đơn vị. Tương tự, các nút bấm ở mỗi cột cũng được Phát thiết kế để tăng các ô trên cột đó lên ~1~ đơn vị. Tuy nhiên, mỗi ô trên bảng chỉ có thể hiển thị được các số từ ~0~ đến ~k-1~ nên nếu giá trị của một ô tăng lên ~k~ thì giá trị ô đó lập tức trở về ~0~. (Xem ví dụ bên dưới với ~r=2~, ~c=3~ và ~k=3~ để hiểu rõ hơn)

Sau một lúc bấm nút, Phát đã tìm ra bảng yêu thích của cậu. Cậu lập tức đi lấy giấy bút để ghi chép lại nó. Tuy nhiên trong lúc cậu đi khỏi, Hiệp đã đến và xáo mất bảng của cậu. Phát rất muốn khôi phục lại bảng nhưng cậu chỉ nhớ được giá trị của ~q~ ô.

Trong lúc đang tìm lại bảng yêu thích của mình thì Phát nhận được thông báo đến trường học trực tiếp. Thế nhưng chưa kịp vui mừng vì được gặp thầy cô, bạn bè thì Phát nhận được một tin sét đánh: "Thầy sẽ chấm vở ghi để lấy điểm".

Phát hoảng hốt vì những ngày học online Phát chỉ mở điện thoại nghe bài giảng cho vui rồi nằm ngủ chứ không ghi chép gì cả. Thời gian thì rất gấp mà Phát lại muốn tìm ra bảng đó càng sớm càng tốt. Nhưng trong cái khó ló cái khôn, Phát nhận ra mình có thể đem bài toán này vào contest Bedao Hay Không? Hay Hay để nhờ các bạn giải hộ trong lúc Phát đi chép bài.

Các bạn hãy giúp Phát tìm ra cách nhanh nhất (tổng số lần bấm nút ít nhất) để khôi phục lại bảng yêu thích của cậu từ bảng ban đầu với giá trị tất cả các ô bằng ~0~ (và học bài nhớ ghi chép bài đầy đủ, đừng như Phát nha :))))

Input

• Dòng đầu tiên chứa bốn số nguyên ~r~, ~c~, ~q~, ~k~ (~1 \le r, c \le 10^5~, ~1 \le q \le \min(r \cdot c, 3 \cdot 10^5)~, ~2 \le k \le 10^9~).
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa ba số nguyên ~x_i~, ~y_i~, ~v_i~ thể hiện Phát nhớ được giá trị của ô ~(x_i, y_i)~ là ~v_i~ (~1\le x_i \le r~, ~1 \le y_i \le c~, ~0 \le v_i < k~, ~x_i \ne x_j~ hoặc ~y_i \ne y_j~ với mọi ~i \ne j~).

Output

Nếu Phát nhớ nhầm, in ra ~-1~. Ngược lại, in ra ba dòng:

• Dòng đầu tiên in ra một số nguyên là số lần bấm nút ít nhất Phát cần để khôi phục lại bảng.
• Dòng thứ hai in ra ~r~ số nguyên, số thứ ~i~ là ~row_i~ - số lần bấm nút ở hàng ~i~. (~0 \le row_i < 2^{31}~)
• Dòng thứ ba in ra ~c~ số nguyên, số thứ ~j~ là ~col_j~ - số lần bấm nút ở cột ~j~. (~0 \le col_j < 2^{31}~)

Nếu có nhiều hơn một phương án, bạn chỉ cần in ra một phương án bất kì.

Subtask

• Subtask 1 (20% số điểm): ~r \cdot c=q~, ~k = 2~
• Subtask 2 (30% số điểm): ~k \le 500~
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm

Sample Input 1

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

Sample Output 1

5
1 2
0 0 2

Sample Input 2

3 3 3 4
1 2 3
2 1 2
3 3 3

Sample Output 2

8
1 1 1
1 2 2

Sample Input 3

2 2 4 4
1 1 0
1 2 1
2 1 2
2 2 0

Sample Output 3

-1

Giữa tình hình dịch bệnh căng thẳng, Bedao High School for Gifted Students cần lập một kế hoạch cụ thể để đưa học sinh trở lại trường nhanh nhất có thể. Trước mắt do yêu cầu của Bộ Y Tế, trường học sẽ phải chia học sinh ra hai nhóm và theo học 2 ca khác nhau (sáng và chiều).

Trường học gồm có ~N~ học sinh đánh số từ ~1~ tới ~N~. Do dịch bệnh phức tạp, các bạn học sinh bắt buộc phải học online trong quãng thời gian rất dài, và từ đó đã xảy ra ~M~ mâu thuẫn giữa các cặp học sinh, khiến các học sinh này không thể học chung ca với nhau. Mâu thuẫn thứ ~i~ xảy ra giữa hai bạn ~u_i~ và ~v_i~, tuy nhiên do có tin nhà trường cho quay trở lại học, hai bạn này sẽ cố gắng giảng hoà và có thể học chung một ca với nhau sau ~i~ ngày. Nếu có nhiều mâu thuẫn xảy ra giữa cùng một cặp học sinh, số ngày cần để giảng hoà sẽ là chỉ số ~i~ lớn nhất biểu diễn cặp mâu thuẫn đó.

Ngoài việc lên kế hoạch dựa trên các cặp mâu thuẫn đã biết trước, nhà trường cũng cần chuẩn bị cho ~Q~ tình huống khác nhau, trong đó tình huống thứ ~i~ biểu diễn một mâu thuẫn không thể giảng hoà giữa hai bạn ~a_i~ và ~b_i~. Với mỗi tình huống, bạn hãy giúp nhà trường xác định số ngày tối thiểu cần thiết để các bạn giảng hoà với nhau trước khi có thể chia ~N~ học sinh vào hai ca học để việc học tập trực tiếp có thể được thực hiện.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~N, M, Q~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i \neq v_i, u_i, v_i \leq n)~ biểu diễn mâu thuẫn thứ ~i~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a_i~ và ~b_i~ ~(a_i \neq b_i, a_i, b_i \leq n)~ biểu diễn tình huống thứ ~i~.

Output

• In ra ~Q~ số nguyên không âm trên ~Q~ dòng, số nguyên thứ ~i~ biểu diễn số ngày ít nhất cần để chờ các học sinh giảng hoà trước khi trường có thể quay lại học. Nếu không cần thiết phải giảng hoà, in ra ~0~.

Subtask

• Subtask 1 (50% số điểm): ~N, M, Q \leq 2000~.
• Subtask 2 (50% số điểm): ~N, M, Q \leq 5 \times 10^{5}~.

Sample Input 1

3 3 2
1 2
2 3
3 1
1 2
3 1

Sample Output 1

2
1

Sample Input 2

4 3 2
1 3
1 2
2 4
4 2
4 1

Sample Output 2

0
2

Sau buổi tan học, ngfam rủ iostream chơi trò xếp ghép hình. Bộ ghép hình của ngfam gồm có một bảng với kích thước ~2^k \times 2^k~. Các hàng trong bảng được đánh số từ ~0~ đến ~2^k - 1~ từ trên xuống dưới, và các cột được đánh số từ ~0~ đến ~2^k - 1~ từ trái qua phải. Ô ở hàng thứ ~r~ và cột ~c~ được biểu diễn bởi cặp số ~(r, c)~. Ngoài ra bộ ghép hình có ~\frac{4^k - 1} 3~ miếng ghép hình chữ ~\texttt{L}~, được phân loại theo góc quay như dưới đây.

Tên của các miếng ghép là viết tắt của vị trí góc phần tư trống của miếng ghép: Top Left, Top Right, Bottom Right và Bottom Left.

Với bộ ghép hình này, bảng có thể được điền vào, và có duy nhất một ô trống không được điền. Ví dụ ta có thể điền vào bảng ~2^3 \times 2^3~ để ô ~(2, 4)~ trống như sau.

ngfam đố iostream điền vào bảng, sao cho ô ~(r, c)~ được bỏ trống. Nhưng không chỉ một lần, mà iostream lúc nào cũng có cách điền thỏa mãn yêu cầu của ngfram. Vì cảm thấy rằng trò chơi quá đơn giản, nên lần này iostream đố ngược lại ngfam. Và câu đố của iostream cũng ngược luôn: cho số ~k~ và số lượng miếng ghép từng loại, hãy xem ô nào sẽ là ô trống không được điền mà không được phép xoay các miêng ghép.

Đến bây giờ ngfam vẫn đang rất bí. Hãy giúp ngfam tìm đáp án cho câu đó của iostream, hoặc chỉ ra rằng không có cách điền nào thỏa mãn yêu cầu của iostream.

Input

Mỗi test bao gồm nhiều test case. Dòng đầu tiên của mỗi test chứa số lượng số test case ~t~ (~1 \le t \le 10^5~). Mỗi test case được mô tả như sau.

Mỗi test case gồm nhất một dòng chứa số nguyên ~k~ (~1 \le k \le 30~) là tham số thể hiện kích thước bảng, tiếp đó là bốn số nguyên ~cnt_\texttt{TL}~, ~cnt_\texttt{TR}~, ~cnt_\texttt{BR}~, và ~cnt_\texttt{BL}~ (~0 \le cnt_\texttt{TL}, cnt_\texttt{TR}, cnt_\texttt{BR}, cnt_\texttt{BL} \le \frac{4^k - 1} 3~) — số lượng các miếng ghép loại ~\texttt{TL}~, ~\texttt{TR}~, ~\texttt{BR}~ và ~\texttt{BL}~ lần lượt theo thứ tự.

Output

Với mỗi test case, in ra một dòng duy nhất chứa hai số nguyên ~r, c~ — vị trí hàng và cột của ô bị trống trên bảng trong trường hợp có đáp án. Trong trường hợp không có đáp án, in ra một dòng duy nhất chứa số ~-1~.

Trong trường hợp có nhiều đáp án thỏa mãn đề bài, hãy in ra đáp án bất kì.

Subtask

• Subtask 1 (20% số điểm): ~1 \le k \le 9~.
• Subtask 2 (80% số điểm): Không có ràng buộc gì thêm.

Sample Input

5
3 4 3 6 8
2 1 2 1 1
3 6 6 3 6
4 17 48 13 7
6 344 317 339 365

Sample Output

7 2
1 2
-1
-1
53 5

Note

Các hình dưới đây lần lượt là cách điền cho ví dụ 1, 2 và 5.