Trong giờ Toán, AP được học về Scientific notation, Thầy giáo nói với AP là kí hiệu ~AeB=A*10^B~. AP ngay lập tức muốn đố các bạn như sau:

Cho ~2~ số ~X~ và ~Y~ được biểu thị dưới dạng ~AeB~ hay (~A*10^B~), so sánh ~X~ và ~Y~.

Input

• Dòng đầu chứa ~Q~ ~(Q \leq 100000)~ là số truy vấn.

• ~Q~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên không âm ~A_x, B_x, A_y, B_y~ để biểu thị ~2~ số ~X={A_x}e{B_x}~ và ~Y={A_y}e{B_y}~.

• Dữ liệu đảm bảo rằng ~0 \leq X, Y \leq 10^{18}~ và ~B_x, B_y~ là các số nguyên không âm.

Output

• ~Q~ dòng, mỗi dòng in ra kết quả theo định dạng sau:

• Nếu ~X~ bé hơn ~Y~, in ra X < Y.

• Nếu ~X~ lớn hơn ~Y~, in ra X > Y.

• Nếu ~X~ bằng ~Y~, in ra X = Y.

Sample Input

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

Sample Output

X < Y
X > Y
X < Y
X > Y
X < Y

Trong vũ trụ bao la, có một nơi được gọi là "Đại Lục Đấu Khí". Ở đây không có các hệ ma pháp, chỉ có đấu khí. Người người tu luyện đấu khí, đợi đến một ngày đột phá bình cảnh, tiến lên một cảnh giới mới: Đấu Khí, Đấu Giả, Đấu Sư, Đại Đấu Sư, Đấu Linh, ..., Đấu Thánh, Đấu Đế. Ở thế giới này, cá lớn nuốt cá bé, cường giả vi tôn. Vì vậy sức mạnh ở đây là yếu tố quan trọng nhất.

iostream tu luyện ~N~ loại võ công, mỗi loại được đánh số từ ~1~ đến ~N~. Loại võ công thứ ~i~ có sức mạnh là một số nguyên dương ~a_i~ ~(a_i \leq 10^9)~. Sức mạnh của iostream là số nguyên dương ~X~ lớn nhất mà mọi phần tử của dãy ~a_1, a_2, a_3, …, a_N~ đều chia hết cho ~X~. Khi đột phá một cảnh giới, iostream có thể thay đổi giá trị của một số trong dãy bằng một giá trị nguyên dương bất kì từ ~1~ đến ~10^9~. Hôm nay là ngày iostream đột phá từ Đấu Sư lên Đại Đấu Sư, nhưng vẫn chưa biết nên thay đổi số nào trong ~N~ số đó để đạt được sức mạnh lớn nhất, các bạn coder hãy giúp iostream tìm ra sức mạnh lớn nhất có thể nhé!

Input

• Dòng đầu tiên chứa duy nhất số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, …, a_N (a_i \leq 10^9)~

Output

• Duy nhất một dòng chứa sức mạnh của iostream sau khi đột phá.

Sample Input:

5
4 4 3 12 8

Sample Output:

4

Subtask:

• ~30\%~ số test có ~N \leq 10^3~
• ~70\%~ số test có ~N \leq 10^6~

AP là một người siêu thông minh nhưng bị mắc bệnh ám ảnh cưỡng chế. Bất kỳ dữ liệu gì anh cũng phải mã hóa nó thành dạng chuỗi ký tự. Lần này AP có một số ~n~ và dãy ~a_1, a_2, ..., a_n~, anh muốn mã hóa nó thành chuỗi ký tự chỉ gồm các chữ cái in thường. Chuỗi gồm ~n~ đoạn, đoạn thứ ~i~ có độ dài ~a_i~ và phải thỏa mãn điều kiện:

• Nếu ~i~ là số lẻ thì các ký tự trong đoạn thứ ~i~ phải thỏa mãn ký tự đứng sau có thứ tự từ điển bé hơn ký tự đứng trước. Lưu ý rằng ký tự đầu tiên của đoạn ~i~ này có thứ tự từ điển bé hơn ký tự cuối cùng của đoạn ~i-1~.

• Nếu ~i~ là số chẵn thì các ký tự trong đoạn thứ ~i~ phải thỏa mãn ký tự đứng sau có thứ tự từ điển lớn hơn ký tự đứng trước. Lưu ý rằng ký tự đầu tiên của đoạn ~i~ này có thứ tự từ điển lớn hơn ký tự cuối cùng của đoạn ~i-1~. (với ~i>1~)

• Ký tự đầu tiên của đoạn ~1~ luôn là ký tự '~z~'.

Hãy tìm chuỗi ký tự thỏa mãn đề bài.

Input

• Dòng đầu tiên chứa số ~Q~ là số lượng truy vấn.
• ~Q~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~n~ là số đoạn trong chuỗi ký tự và dãy ~a_1, a_2, a_3, ..., a_n~ với ~a_i~ là độ dài đoạn thứ ~i~. ~(1 \le a_i \le 26)~

Output

• Ứng với mỗi truy vấn, in ra chuỗi ký tự thỏa mãn đề bài. Mỗi truy vấn in ra trên một dòng.
• Trong trường hợp có nhiều đáp án, in ra chuỗi ký tự có thứ tự từ điển bé nhất. Ngược lại nếu không tìm được chuỗi ký tự thỏa mãn in ra ~-1~.

Sample Input

2
2
26 3
3
2 3 3

Sample Output

zyxwvutsrqponmlkjihgfedcbabcd
zabcdcba

Subtask

• ~30\%~ số test có ~1 \le Q \le 10, 1 \le n \le 2~
• ~70\%~ số test tiếp theo có ~1 \le Q \le 50, 1 \le n \le 2*10^4~

Một lớp học có ~n~ bàn xếp theo hàng dọc. Bàn thứ ~i~ có ~x_i~ học sinh, học sinh thứ ~j~ của bàn ~i~ có số điểm là ~a_{ij}~. Một dãy bàn được gọi là có điểm chung là ~K~ nếu mỗi bàn trong dãy đều có ít nhất ~1~ học sinh đạt điểm ~K~.

Bạn hãy tìm số lượng bàn nhiều nhất liên tiếp nhau sao cho điểm chung của dãy bàn này là ~K~.

Input

• Dòng đầu chứa ~2~ số nguyên ~n~ và ~Q~ ~(1 \leq n, Q \leq 10^3)~ lần lượt là số lượng bàn và số lượng truy vấn.

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~x_i~ ~(x_i \leq 10^3)~ là số học sinh của bàn ~i~ và dãy gồm ~x_i~ số nguyên không âm không quá ~10^6~ là điểm số của ~x_i~ học sinh đó.

• ~Q~ dòng tiếp theo, dòng thứ ~j~ chứa một số nguyên ~K_j~ không quá ~10^6~ là dữ liệu của truy vấn thứ ~j~.

Output

• Gồm ~Q~ dòng. Ứng với truy vấn thứ ~j~ bạn phải trả về số lượng bàn nhiều nhất liên tiếp nhau sao cho điểm chung của dãy bàn này là ~K_j~. Mỗi truy vấn in ra trên ~1~ dòng.

Sample Input

3 2
2 2 5
3 2 9 3
2 5 1
2 
5

Sample Output

2
1

Subtask

• ~50\%~ số test thỏa mãn ràng buộc ~1 \leq n, q \leq 100, 1 \leq m, x, a_i \leq 100~
• ~50\%~ số test thỏa mãn ràng buộc ~1 \leq n, m, q \leq 1000, 1 \leq x, a_i \leq 10^6~

Dạo gần đây do quá lười biếng, chó vàng đã bị chị Hiền lôi đầu ra bắt phải làm việc. Mệt mỏi và chán nản, chó vàng quyết định lại một lần nữa sủi công việc của mình. Nhưng Hiền đã cao tay hơn đi trước một bước, Hiền đã tóm cổ chó vàng nhét vào trong một mê cung, và bắt chó vàng phải nghĩ ra bài mới thì chó mới thoát khỏi mê cung được.

Phận là một con chó, lại bị đàn áp như thế, thật không thể chấp nhận được. Vì thế, chó vàng đã nhờ đến sự trợ giúp của bạn, một lập trình viên cao tay. Bạn hãy giúp chó tìm đường đi thoát khỏi mê cung nhanh nhất có thể.

Mê cung mà chó vàng bị nhốt có thể được biểu diễn dưới dạng một ma trận gồm ~N~ hàng và ~M~ cột. Các hàng được đánh số từ ~1~ đến ~N~ từ trên xuống, các cột được đánh số từ ~1~ đến ~M~ từ trái sang phải. Ô giao giữa hàng thứ ~i~ và cột thứ ~j~ được kí hiệu là ô (~i~, ~j~). Khi đứng ở ô (~i~, ~j~), chó vàng có thể di chuyển sang một trong bốn hướng Bắc, Đông, Nam, Tây, đến một trong các ô (~i - 1~, ~j~), (~i~, ~j + 1~), (~i + 1~, ~j~), (~i~, ~j - 1~) với thời gian di chuyển là một giây.

Một số ô trong ma trận sẽ có cột đá, khi đứng trong một ô có cột đá, chó vàng có thể đạp cột đá để phóng đến một ô cùng hàng hoặc cùng cột, sao cho không có bất kì cột đá nào khác trên đường bay của chó vàng trừ ô xuất phát và ô kết thúc. Chó vàng bay rất nhanh, nên có thể xem thời gian bay là một giây.

Hiện tại chó vàng đang đứng ở ô (~1~, ~1~), để thoát ra khỏi mê cung, chó vàng cần đến được ô (~N~, ~M~). Hãy tìm đường đi nhanh nhất để chó vàng có thể thoát ra khỏi mê cung.

Input

Dòng đầu tiên gồm chứa ~2~ số nguyên ~N~ và ~M~ ~(1 \le N, M \le 1000)~ mô tả ma trận A.

~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên mô tả ma trận, A(i, j) = 1 hoặc 0, tương ứng ở ô (i, j) có cột đá hay không.

Output

In ra một số nguyên là thời gian nhanh nhất để chó vàng có thể thoát ra khỏi mê cung.

Sample Input

4 5
0 1 0 0 0
1 0 0 0 1
1 0 1 0 0
0 0 1 0 0

Sample Output

3

Subtask

• Subtask 1: 10% số lượng bộ test có ~1 \le N * M \le 10~
• Subtask 2: 30% số lượng bộ test có ~1 \le N, M \le 100~
• Subtask 3: 60% số lượng bộ test có ~1 \le N, M \le 1000~

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đào có ~m~ cây cầu được xây sẵn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_j~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~

• ~D~ ~j~ có tác dụng xóa đi cây cầu thứ ~j~ nối hai hòn đảo ~u_j~ và ~v_j~

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input

• Dòng thứ nhất chứa ba số nguyên ~n~, ~m~, ~q~ ~(n, m, q \leq 3*10^{5})~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1, w_2, ..., w_n~ ~(w_i \leq 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_j~ và ~v_j~
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Sample Input

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output

15
11
11
11
17
17
17
9