Quân đang học về thì hiện tại tiếp diễn (Present Continuous), và được giao một bài tập như sau:

"Fill in the bank with suitable form of the verb "to be"" (điền vào chỗ trống động từ dạng to be phù hợp).

Quân được cho một câu có dạng:

~\text{S + "___" + V_ing + O}~

Trong đó:

- ~S~ là Subject (chủ ngữ), ~S~ có thể là một đại từ hoặc một tên riêng.

- ~V~ là Verb (động từ).

- ~O~ là Object (tân ngữ), ~O~ có thể là người hoặc vật, động vật.

Quân cần điền vào ~\text{"___"}~ một dạng đúng của động từ to be ~\text{(am/is/are)}~ ứng với chủ ngữ ~S~ của câu.

Input

Một dòng duy nhất chứa xâu ~s~ có dạng như đã cho. Dữ liệu được cho đảm bảo không có tên riêng trùng với đại từ.

Output

Một xâu duy nhất chứa động từ dạng to be phù hợp ~\text{(am/is/are)}~.

Sample Input 1

He ___ playing football

Sample Output 1

is

Sample Input 2

Adele ___ rolling in the deep

Sample Output 2

is

Sample Input 3

They ___ fighting against Thanos

Sample Output 3

are

Sample Input 4

Wanda ___ sleep walking

Sample Output 4

is

Sample Input 5

Mr.Wilson ___ talking to Jessica

Sample Output 5

is

Sample Input 6

I ___ hacking NASA

Sample Output 6

am

Notes

Chủ ngữ	+	Chia động từ
~\text{I}~		~\text{am}~
~\text{He}~		~\text{is}~
~\text{She}~		~\text{is}~
~\text{It}~		~\text{is}~
~\text{We}~		~\text{are}~
~\text{They}~		~\text{are}~
~\text{You}~		~\text{are}~
~\text{Tên riêng}~		~\text{is}~

Trung có hai dãy ~a~, ~b~ gồm ~n~ phần tử. Trung sẽ thực hiện thao tác sau ~k~ lần:

• Chọn một vị trí ~i~ bất kì, và tăng ~a_i~ hoặc ~b_i~ lên ~1~ đơn vị.

Trung muốn ~\sum \limits_{i = 1}^{n} a_i \cdot b_i~ đạt giá trị lớn nhất có thể, hay nói cách khác, tổng của tích các cặp số nằm ở vị trí ~i~ là lớn nhất có thể. Hãy thực hiện ~k~ thao tác một cách hợp lý để Trung đạt được mục tiêu ấy nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^5, 1 \le k \le 10^9~) — số phần tử của dãy ~a~, ~b~ và số thao tác được thực hiện.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^5~) — các phần tử của dãy ~a~.

Dòng tiếp theo chứa ~n~ số nguyên dương ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le 10^5~) — các phần tử của dãy ~b~.

Output

Một dòng duy nhất chứa đáp án của bài toán: giá trị lớn nhất có thể của ~\sum \limits_{i = 1}^{n} a_i \cdot b_i~ sau khi thực hiện ~k~ thao tác.

Scoring

Subtask	Điểm	Giới hạn
1	~24~	~n \le 3000~
2	~76~	không có giới hạn gì thêm

Sample Input 1

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

Sample Output 1

171

Lihwy và FireGhost là hai đá thủ nổi tiếng trong cộng đồng VNOI. Để cạnh tranh danh hiệu "vua đá", Lihwy đã đề xuất FireGhost cùng chơi một trò chơi:

Có ~n~ viên đá, hai người chơi sẽ lần lượt thực hiện các thao tác sau (Lihwy đi trước):

• Nếu số viên đá còn lại là ~x~, người chơi hiện tại phải bốc ra ngoài ~k \ge 1~ viên đá sao cho ~\gcd(k, x) = 1~.

Ai là người bốc viên đá cuối cùng ra ngoài sẽ thắng. Nếu cả hai chơi hợp lý, ai sẽ là người thắng?

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 100~) — số testcase của bài toán.

Dòng thứ ~i~ trong ~t~ dòng tiếp theo chứa số nguyên dương ~n~ (~1 \le n \le 10^9~) thể hiện một testcase — số viên đá ban đầu trong trò chơi.

Output

Với mỗi testcase, in ra Lihwy hoặc FireGhost (không quan trọng kí tự in hoa hay thường) tương ứng với người thắng trò chơi.

Scoring

Subtask	Điểm	Giới hạn
1	~25~	tổng của ~n~ trong tất cả các testcase không vượt quá ~5000~
2	~75~	không có giới hạn gì thêm

Sample Input 1

2
1
2

Sample Output 1

Lihwy
FireGhost

Notes

Ở test ví dụ đầu tiên, Lihwy chỉ cần bốc ~1~ viên đá và chiến thắng.

Ở test ví dụ thứ hai, Lihwy chỉ có một lựa chọn duy nhất là bốc ~1~ viên đá, còn FireGhost sẽ bốc viên đá còn lại ở lượt chơi tiếp theo và chiến thắng.

Sau những giờ học căng thẳng, Quân và Hiển chơi domino để xốc lại tinh thần. Mỗi quân domino là một tấm thẻ gồm hai nửa dính liền vào nhau, trên mỗi nửa ghi các chấm với số lượng từ ~1~ đến ~6~. Hiện Quân và Hiển đang có ~n~ tấm domino, quân thứ ~i~ có ghi ~a_i~ chấm ở nửa trên và ~b_i~ chấm ở nửa dưới.

Độ chênh lệch của các quân domino được tính bằng trị tuyệt đối hiệu số lượng các chấm ở nửa trên và nửa dưới. Ví dụ trong hình trên: tổng số chấm ở nửa trên là ~1+1+2+1=5~, tổng số chấm ở nửa dưới là ~2+2+4+3=11~, độ chênh lệch là ~|11-5|=6~.

Vì là người không thích sự chênh lệch, Quân muốn đảo một số quân domino (tức nửa trên thành nửa dưới, nửa dưới thành nửa trên) sao cho độ chênh lệch sau cùng là bé nhất có thể.

Yêu cầu: Bạn hãy giúp Quân tìm độ chênh lệch bé nhất đó nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1\le n\le 10^5~) — số quân domino.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ (~1\le a_i\le 6~) — số chấm ghi ở nửa trên của các quân domino.

Dòng thứ ba chứa ~n~ số nguyên dương ~b_1,b_2,\dots,b_n~ (~1\le b_i\le 6~) — số chấm ghi ở nửa dưới của các quân domino.

Output

In ra hai dòng:

• Dòng đầu tiên in ra một số nguyên dương là chênh lệch trong phương án tìm được.

• Dòng thứ hai in ra số nguyên dương ~m~ (~0 \le m \le n~) thể hiện số domino cần đảo trong phương án tìm được; sau đó in ra ~m~ số nguyên dương ~p_1, p_2, \ldots, p_m~ thể hiện chỉ số của các domino cần đảo.

Scoring

Subtask	Điểm	Giới hạn
1	~15~	~n\le 20~
2	~25~	~n\le 40~
3	~20~	~n\le 1000~
4	~40~	không có giới hạn gì thêm

Sample Input 1

4
2 1 2 1
2 2 4 3

Sample Output 1

1
1 3

Trung là một người thích ăn cay vô cùng. Hôm nay cậu đang tham gia thử thách ăn cay siêu khủng khiếp.

Cho ~n~ miếng pizza siêu cay được đặt theo vòng tròn, các miếng pizza được đánh số từ ~0~ đến ~n-1~, miếng thứ ~i~ kề với miếng ~(i + 1) \bmod n~. Miếng thứ ~i~ có độ cay là ~a_i~. Để ăn được miếng pizza này, Trung phải có sức chịu đựng là ~k \ge a_i~. Sau khi ăn xong, sức chịu đựng của Trung sẽ được tăng lên bằng ~k + a_i~.

Hãy giúp Trung tìm sức chịu đựng ban đầu nhỏ nhất có thể để có thể hoàn thành thử thách, biết rằng Trung sẽ được phép ăn miếng pizza đầu tuỳ ý, nhưng sau đó Trung chỉ ăn các miếng mà kề với tối đa một miếng khác.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~ — số lượng miếng pizza.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^{13})~. Các miếng pizza này được xếp theo vòng tròn.

Output

In ra một số nguyên duy nhất là sức chịu đựng ban đầu nhỏ nhất mà Trung cần có để hoàn thành được thử thách.

Scoring

Subtask	Điểm	Giới hạn
1	~20~	~a_i \le 100, n \le 15~
2	~30~	~n\le 1000~
3	~50~	không có giới hạn gì thêm

Sample Input 1

4
10 20 15 1

Sample Output 1

9

Notes

Với sức chịu đựng ban đầu là ~9~, Trung có thể chọn ăn lần lượt các miếng pizza ~4~, ~1~, ~3~ và ~2~.

Cho trước số nguyên dương ~n~, ~w~ và 2 dãy số nguyên ~a_1, a_2, \ldots, a_n~ và ~b_1, b_2, \ldots, b_n~. Tìm 2 dãy số không âm ~x_1, x_2, \ldots, x_n~ và ~y_1, y_2, \ldots, y_n~ sao cho: $$\sum_{i = 1}^n x_i = W$$ $$\sum_{i = 1}^n y_i = W$$ $$\sum_{i = 1}^n (x_i \cdot y_i)^2 = 0$$

Và giá trị của biểu thức

$$V=(\sum_{i = 1}^n a_i x_i)(\sum_{i = 1}^n b_i x_i) + (\sum_{i = 1}^n a_i y_i)(\sum_{i = 1}^n b_i y_i)$$

là lớn nhất. In ra giá trị lớn nhất của ~V~.

Input

Dòng đầu gồm 2 số nguyên dương ~n~, ~W~ ~(2 \leq n \leq 1000, 1 \leq W \leq 100)~.

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \leq |a_i| \leq 100)~.

Dòng tiếp theo gồm ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ ~(1 \leq |b_i| \leq 100)~.

Output

In ra giá trị lớn nhất của ~V~. Đáp án được chấp nhận nếu sai số so với đáp án chuẩn không vượt quá ~10^{-6}~.

Scoring

Subtask	Điểm	Giới hạn
1	~20~	~n = 2~
2	~30~	~n \le 50~
3	~50~	không có giới hạn gì thêm

Sample Input 1

2 2
0 1
1 0

Sample Output 1

0.0000000000

Sample Input 2

4 1
0 1 0 -1
1 0 -1 0

Sample Output 2

0.5000000000

Notes

Với ví dụ 1, chỉ có hai lựa chọn cho hai dãy ~x, y~:

• ~x = [0, 2]~, ~y = [2, 0]~. Khi đó $$V = (0 \times 0 + 1 \times 2) (1 \times 0 + 0 \times 2) + (0 \times 2 + 1 \times 0) (1 \times 2 + 0 \times 0) = 0$$

• ~x = [2, 0]~, ~y = [0, 2]~. Vì vai trò ~x, y~ tương đương, tương tự trường hợp đầu, ~V = 0~.

Với ví dụ 2, một trong các cách chọn ~x, y~ là ~x = [0.5, 0.5, 0, 0]~, ~[y = 0, 0, 0.5, 0.5]~. Khi đó $$V_x = (\sum_{i = 1}^n a_i x_i)(\sum_{i = 1}^n b_i x_i)$$ $$V_x = [0 \times 0.5 + 1 \times 0.5 + 0 \times 0 + (-1) \times 0] \times[1 \times 0.5 + 0 \times 0.5 + (-1) \times 0 + 0 \times 0]$$ $$V_x = 0.5 \times 0.5 = 0.25$$

$$V_y = (\sum_{i = 1}^n a_i y_i)(\sum_{i = 1}^n b_i y_i)$$ $$V_y = [0 \times 0 + 1 \times 0 + 0 \times 0.5 + (-1) \times 0.5] \times [1 \times 0 + 0 \times 0 + (-1) \times 0.5 + 0 \times 0.5]$$ $$V_y = (-0.5) \times (-0.5) = 0.25$$

Cộng lại ta có ~V = V_x + V_y = 0.5~. Có thể chứng minh đây là giá trị lớn nhất của ~V~ có thể đạt được.