KazamaHoang đang dạy FireGhost tập đánh cờ vua. Sau khi giải thích về cách quân xe hoạt động, chỉ có thể ăn những quân cùng hàng hoặc cùng cột với nó, KazamaHoang đã đố FireGhost một bài toán như sau:

Cho một bàn cờ vua có ~n~ hàng và ~m~ cột. Hãy tìm cách đặt ~k~ quân xe vào ~k~ ô khác nhau sao cho các quân xe đôi một không ăn nhau.

FireGhost tuy thông minh hơn người nhưng vẫn phải bó tay trước bài toán hóc búa như vậy. Hãy tìm anh ấy tìm ra đáp án nhé!

Input

• Một dòng duy nhất nhập ba số nguyên ~n~, ~m~, ~k~ ~(1 \le n, m \le 500, 1 \le k \le n * m)~.

Output

• In ra ~k~ dòng, dòng thứ ~i~ là hai số nguyên ~x_i~ và ~y_i~ lần lượt là chỉ số hàng và cột của quân xe thứ ~i~. Nếu có nhiều cách đặt thì in ra một cách bất kì. Nếu không tồn tại cách đặt ~k~ quân xe, in ra giá trị ~n + m + k~.

Sample Input

1 1 1

Sample Output

1 1

Cho dãy ~a~ độ dài ~n~ và ~q~ thông tin thuộc một trong ~3~ loại sau:

• ~1\ l\ r\ x~ ~(1 \le l \le r \le n,\ 1 \le x \le 10^8)~: các phần tử trong đoạn ~l\ r~ được tăng thêm ~x~.

• ~2\ i~: thông tin thứ ~i~ là thông tin sai (dữ liệu đảm bảo thông tin thứ ~i~ thuộc loại ~1~ hoặc loại ~2~ và thông tin thứ ~i~ đã xuất hiện trước đó).

• ~3\ l\ r~ ~(1 \le l \le r \le n)~: tính tổng các số trong đoạn ~l\ r~.

Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm, biết rằng những thông tin đang không bị thông tin loại ~2~ chỉ vào thì chắc chắn là thông tin đúng, và không có hai thông tin loại ~2~ nào giống hệt nhau.

Input

• Dòng đầu nhập ~2~ số ~n~ và ~q~ ~(1 \le n,\ q \le 10^5)~ ~-~ tương ứng là số phần tử của dãy ~a~ và số thông tin .

• Dòng thứ hai nhập ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^8)~- tương ứng là các phần tử của dãy ~a~

• Trong ~q~ dòng tiếp theo, mỗi dòng nhập một thông tin thuộc một trong ~3~ loại theo định dạng như đề bài.

Output

• Với mỗi truy vấn thuộc loại ~3~, in ra tổng cần tìm.

Subtask

• ~20\%~ số test khác có ~1 \le n, q \le 2000~.

• ~80\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input

5 6
0 0 0 0 0
1 1 2 1
3 1 3
2 1
3 1 3
2 3
3 1 3

Sample Output

2
0
2

Bé Naot đang học cách để nội suy đa thức, kết quả nội suy thu được từ thuật toán của bé Naot là ~t~ số hữu tỉ được viết dưới dạng số ~k~-phân.

Bé Naot muốn chuyển đổi các số ~k~-phân này về các phân số dưới dạng thập phân để tiện cho việc tính toán cũng như để đạt được độ chính xác tuyệt đối. May mắn thay bé Naot đủ thông minh để nhận ra có một số số ~k~-phân trong kết quả là những số ~k~-phân vô hạn tuần hoàn, vì thế bé Naot đã viết những số ~k~-phân thu được thành một định dạng đặc biệt.

Naot sẽ viết một số ~k~-phân dưới dạng cặp xâu ~(a, b)~, trong đó:

• ~a~ là phần không vô hạn tuần hoàn, ~a~ luôn được viết dưới dạng ~d\text.e~, trong đó ~d~ là phân nguyên, ~e~ là phần ~k~-phân.

• ~b~ là phần vô hạn tuần hoàn.

• ~b~ đã được thu gọn ngắn nhất (Ví dụ: ~b = 2323~ sẽ được viết thành ~b = 23~).

Bé Naot không đủ thông minh để tìm ra số hữu tỉ từ biểu diễn ~k~-phân của nó, nhưng bé biết rằng các số hữu tỉ luôn có thể viết dưới dạng ~\frac{a}{b}~ với ~a~ và ~b~ là các số nguyên với ~b \ne 0~ và phân số đã đưa về dạng tối giản. Các bạn hãy giúp Naot của chúng ta tìm ra số hữu tỉ mà bé muốn nhé!

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(t \le 100)~ là số test.

• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên ~k~ và hai xâu ~a, b~ ~(2 \le k \le 10, 1 \le |a|, |b| \le 6)~, với cặp xâu ~(a, b)~ biểu diễn một số ~k~-phân (~|s|~ thể hiện độ dài của xâu ~s~).

Output

• In ra ~t~ dòng, dòng thứ ~i~ chứa hai số nguyên dương ~a~ và ~b~ được biểu diễn dưới dạng thập phân cho biết ~\frac{a}{b}~ là phân số tối giản biểu diễn số ~k~-phân thứ ~i~. Biết rằng đáp án luôn đảm bảo ~1 \le a, b \le 10^{18}~.

Sample Input

3
3 1.2 0
10 1.5 0
8 1.4 3

Sample Output

5 3
3 2
87 56

Được sinh ra nhằm phục vụ các nhu cầu thiết yếu của con người như phân lô, tách thửa mua bán, tính diện tích, toán học từ lâu đã trở thành một phần không thể thiếu của thế giới. Hình học và Số học có thể được coi là hai nhánh lớn và lâu đời nhất của Toán học, đã xuất hiện từ thời kì cổ đại.

HIện nay, khi khoa học công nghệ phát triển mạnh; Hình học cổ điển đã dần được thay thế bởi Hình học giải tích, song Số học vẫn giữ nguyên vị thế của nó, thậm chí đóng vai trò là khung xương sống cho nền công nghệ hiện đại.

Vì vậy, hôm nay bạn được cho một bài toán số học như sau:

Cho 5 số nguyên dương ~a, b, c, d, k~ ~(a \leq b, c \leq d)~.

Tính tổng các tích ~i \times j~ của các cặp ~(i, j)~ thỏa ~a \leq i \leq b~, ~c \leq j \leq d~ và ~gcd(i, j) = k~. Nói cách khác, hãy tính:

$$\displaystyle\sum_{i = a}^{b}{ \displaystyle\sum_{j = c}^{d} i \times j \times [gcd(i, j) = k]}$$

Kết quả hiện thi dưới dạng phép chia lấy dư (modulo) cho ~10^9 + 7~.

Input

• Dòng đầu chứa một số nguyên dương ~T~ ~(T≤10^5)~ là số bộ dữ liệu (testcase).

• ~T~ dòng tiếp, mỗi dòng chứa năm số nguyên ~a,b,c,d,k~ ~(1≤a≤b≤10^5,1≤c≤d≤10^5,k≤10^5)~ mô tả một bộ dữ liệu.

Output

• ~T~ dòng, mỗi dòng là đáp án cho bộ dữ liệu tương ứng.

Subtask

• Có ~20\%~ số test có ~1\le b,d\le 2000,T=1~.
• Có ~20\%~ số test có ~1\le T, b,d\le 2000, a=c=k=1~.
• Có ~20\%~ số test có ~1\le T,b,d\le 2000,k=1~.
• Có ~20\%~ số test có ~1\le T,b,d\le 2000~.
• Có ~20\%~ số test có ~1\le T,b,d\le 10^5~.

Sample Input

2
1 5 1 5 1
1 5 1 5 2

Sample Output

155
20

Đây là một bài interactive.

Hệ thống có một dãy ~a~ là hoán vị của số tự nhiên từ ~1~ đến ~n~, các phần tử được đánh số từ ~0~. Nhiệm vụ của bạn là tìm được hoán vị này.

Bạn có thể hỏi các truy vấn dưới dạng một dãy ~b~ cũng là hoán vị của số tự nhiên từ ~1~ đến ~n~. Hệ thống sẽ cho biết tổng: ~\displaystyle \sum^{n-1}_{i=0}|a_i-b_i|~.

Bạn cần tìm được hoán vị bằng cách hỏi không quá ~U~ (~U~ là một số cho trước) truy vấn.

Input

• Dòng đầu tiên chứa một số nguyên ~t~ (~t\le 10~) – số test case.

• Dòng đầu tiên của mỗi test case chứa ~n~ (~n\le 500~) và ~U~ – độ dài của hoán vị và số lượt hỏi tối đa.

• Sau khi đọc dòng này bạn sẽ bắt đầu quá trình tương tác.

Interaction

Để hỏi một truy vấn dưới dạng hoán vị ~b~, chương trình của bạn cần in "ask ~b_0\ b_1\ \ldots\ b_{n-1}~".

Sau đó chương trình của bạn cần đọc kết quả ~\displaystyle \sum^{n-1}_{i=0}|a_i-b_i|~ được cung cấp bởi hệ thống.

Để đưa ra đáp án, chương trình của bạn cần in "answer ~p_0\ p_1\ \ldots\ p_{n-1}~" với ~p~ là dãy mà bạn tìm được. Việc đưa ra đáp án không tính vào số câu hỏi. Sau đó chương trình của bạn cần tiếp tục giải các test case còn lại, hoặc dừng lại nếu đã giải hết các test case.

Sau khi in ra một truy vấn, bạn cần xuống dòng và flush output. Để làm điều này, hãy:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;

Subtask

• ~30\%~ số test khác có ~U=1000~.

• ~70\%~ số test còn lại có ~U=750~.

Sample Input

1
2 1000

0

Sample Output

ask 1 2

answer 1 2

lastPledge đang bị truy nã toàn thành phố vì lỡ đánh cắp trái tim của crush! Lúc này, hắn ta đang tìm đường trốn ra nước ngoài, tuy nhiên, vì cả thành phố đều bị phong tỏa, lastPledge đành phải trốn tạm vào một ngôi nhà và án binh bất động để tránh bị cảnh sát tìm thấy.

Thành phố nơi lastPledge đang sống có ~n~ ngôi nhà và ~n - 1~ con đường nối trực tiếp giữa hai căn nhà, sao cho luôn tồn tại đường đi giữa ~2~ ngôi nhà bất kì. Là cảnh sát trưởng của thành phố, FireGhost được giao nhiệm vụ tóm gọn tên trộm. Anh ấy sẽ lặp lại những thao tác sau đến khi bắt được lastPledge:

• FireGhost sẽ chọn một ngôi nhà bất kì, sau đó lục soát căn nhà để tìm kiếm tên trộm. Quá trình này sẽ mất ~1~ tiếng.

• Nếu tìm thấy tên trộm, anh ấy sẽ dừng quá trình tìm kiếm và áp giải tên trộm về đồn cảnh sát.

• Ngược lại, anh ấy sẽ được người dân chỉ điểm: Trong các con đường đi ra khỏi căn nhà hiện tại, con đường nào sẽ dẫn tới nơi tên trộm đang trốn.

Biết rằng FireGhost là một cảnh sát vô cùng thông minh, anh ta luôn chọn phương án tối ưu khi làm việc. Hãy cho biết trong trường hợp xấu nhất anh ta sẽ mất bao nhiêu thời gian để bắt được tên trộm lastPledge.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ — số ngôi nhà trong thành phố (~1 \le n \le 10^5~).

• Dòng tiếp theo gồm ~n - 1~ số nguyên ~p_1, p_2, \ldots, p_{n - 1}~ (~0 \le p_i < i~), thể hiện một con đường nối ~2~ ngôi nhà ~i~ và ~p_i~.

Output

• In ra số giờ ít nhất cần bỏ ra để bắt được tên trộm trong trường hợp xấu nhất.

Subtask

• ~16\%~ số test khác có ~n \le 20~.

• ~36\%~ số test khác có ~n \le 5000~.

• ~48\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
0 1 1 1

Sample Output 1

2

Sample Input 2

8
0 1 2 1 3 5 6

Sample Output 2

3

Notes

Trong test ví dụ đầu tiên, nếu FireGhost không chọn đỉnh ~1~ ở lượt đầu tiên, anh ấy sẽ cần thêm ít nhất ~2~ lượt trong trường hợp xấu nhất.