Trên mặt phẳng ~Oxy~ có ~N~ điểm, điểm thứ ~i~ có tọa độ là ~(x_i, y_i)~. Hãy cho biết khoảng cách Manhattan xa nhất giữa hai điểm bất kì trong ~N~ điểm trên.

Ta định nghĩa khoảng cách Manhattan giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~|x_1 − x_2| + |y_1 − y_2|~.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ với ~(2 \leq N \leq 100)~.

~N~ dòng tiếp theo, mỗi dòng chưa ~2~ số nguyên ~(x_i, y_i)~ ~(-1000 \leq x, y \leq 1000)~ là toạ độ các điểm thứ ~i~ tương ứng .

Output

In ra một số duy nhất, là khoảng cách Manhattan lớn nhất.

Simple Input 1

2
-1 3
1 1

Simple Ouput 1

4

Simple Input 2

4
0 0
1 2
1 3
0 5

Simple Output 2

5

Giải thích

• Ở ví dụ thứ nhất, khoảng cách Manhattan giữa hai điểm là ~|(−1) − 1| + |3 − 1| = 2 + 2 = 4~.
• Ở ví dụ thứ hai, hai điểm ~(0, 0)~ và ~(0, 5)~ có khoảng cách Mantantan lớn nhất.

Cho một ma trận các ô vuông. Ô ~(i, j )~ được định nghĩa là ô vuông nằm trên điểm giao của dòng ~i~ và cột ~j~.

Ban đầu cột đầu tiên của ma trận ô vuông sẽ có giá trị lần lượt là ~1, 2, 3, ...~ Từ cột thứ 2 trở đi thì ô ~(i, j)~ bất kỳ sẽ có giá trị là: ~ (i , j - 1) + (i, 1)~. Ví dụ ~6~ dòng và ~6~ cột đầu của ma trận ô vuông :

Một con rô bốt xuất phát tại ô ~(1, 1)~. Trong mỗi bước robot có thể đi đến một trong bốn ô kề cạnh với ô mà rô bốt đang đứng. Cụ thể, nếu rô bốt đang ở ô ~(i, j)~ thì nó có thể đi đến một trong bốn ô sau: ~(i - 1, j)~, ~(i + 1, j)~, ~(i, j - 1)~, ~(i, j + 1)~. Chú ý, rô bốt không thể đi ra ngoài khỏi bảng ô vuông.

Hãy cho biết số bước đi ít nhất để rô bốt đi đến ô vuông bất kỳ có giá trị là số nguyên ~N~ với ma trận có kích thước là vô hạn.

Input

Đầu vào chứa một số nguyên dương duy nhất ~N~ ~(1 \leq N \leq 100)~.

Output

In ra một số nguyên duy nhất là số bước đi ít nhất cần tìm.

Simple Input 1

6

Simple Output 1

3

Simple Input 2

12

Simple Output 2

5

Cho một ma trận các ô vuông. Ô ~(i, j )~ được định nghĩa là ô vuông nằm trên điểm giao của dòng ~i~ và cột ~j~.

Ban đầu cột đầu tiên của ma trận ô vuông sẽ có giá trị lần lượt là ~1, 2, 3, ...~ Từ cột thứ 2 trở đi thì ô ~(i, j)~ bất kỳ sẽ có giá trị là: ~ (i , j - 1) + (i, 1)~. Ví dụ ~6~ dòng và ~6~ cột đầu của ma trận ô vuông :

Một con rô bốt xuất phát tại ô ~(1, 1)~. Trong mỗi bước robot có thể đi đến một trong bốn ô kề cạnh với ô mà rô bốt đang đứng. Cụ thể, nếu rô bốt đang ở ô ~(i, j)~ thì nó có thể đi đến một trong bốn ô sau: ~(i - 1, j)~, ~(i + 1, j)~, ~(i, j - 1)~, ~(i, j + 1)~. Chú ý, rô bốt không thể đi ra ngoài khỏi bảng ô vuông.

Hãy cho biết số bước đi ít nhất để rô bốt đi đến ô vuông bất kỳ có giá trị là số nguyên ~N~ với ma trận có kích thước là vô hạn.

Input

Đầu vào chứa một số nguyên dương duy nhất ~N~ ~(1 \leq N \leq 10^{12})~.

Output

In ra một số nguyên duy nhất là số bước đi ít nhất cần tìm.

Simple Input 1

6

Simple Output 1

3

Simple Input 2

12

Simple Output 2

5

Xâu lũy thừa bậc ~K~ của một xâu ~S~ là một sâu ~T~ mà ~T~ được tạo thành bằng cách viết ~K~ lần xâu ~S~ liên tiếp nhau. Ví dụ, xâu lũy thừa bậc ~3~ của xâu "abc" là xâu "abcabcabc".

Cho số nguyên ~K~ và ~2~ xâu ~S, T~. Yêu cầu kiểm tra xem xâu ~T~ có phải là lũy thừa bậc ~K~ của xâu ~S~ hay không?

Input

Gồm ~3~ dòng lần lượt là xâu ~S~, xâu ~T~, và số nguyên ~K~ với độ dài mỗi xâu không quá ~1000~ kí tự và ~1 \leq K \leq 1000~.

Output

Nếu xâu T là xâu lũy thừa bậc K của xâu S in "YES", ngược lại in "NO".

Simple Input 1

abc
abcabcabc
3

Simple Output 1

YES

Simple Input 2

abc
abcabcabc
2

Simple Output 2

NO

Simple Input 3

xyz
abc
1

Simple Output 3

NO

Simple Input 4

x
xxxx
4

Simple Output 4

YES

Cho một dãy số ~a_1, a_2, \cdots, a_n~ gồm ~n~ số nguyên dương không lớn hơn ~n~. Xét một số nguyên dương ~x~ bất kì có giá trị từ ~1~ đến ~n~, ta thực hiện phép gán ~x = a_x~ và lặp lại phép gán cho đến khi giá trị của ~x~ sau khi gán không thay đổi thì quá trình được dừng lại.

Ví dụ, nếu dãy ~a~ là ~[1, 4, 2, 1]~ và ~x = 3~ thì:

• Ở bước đầu tiên, với ~x = 3~ thì ~a_3 = 2~ nên ta gán ~x = 2~.

• Ở bước thứ hai, với ~x = 2~ thì ~a_2 = 4~ nên ta gán ~x = 4~.

• Ở bước thứ ba, với ~x = 4~ thì ~a_4 = 1~ nên ta gán ~x = 1~.

• Ở bước thứ tư, với ~x = 1~ thì ~a_1 = 1~ nên ta gán ~x = 1~.

• Do giá trị ~x~ không đổi sau bước thứ tư nên quá trình biến đổi được dừng lại.

Cho ~q~ truy vấn, mỗi truy vấn yêu cầu: cho một số ~x~ ban đầu, hãy in ra số phép biến đổi được thực hiện (trong trường hợp số phép biến đổi là vô hạn thì in ra ~−1~).

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ là độ dài của dãy số ~(3 \leq n \leq 2\cdot10^5)~.

Dòng thứ hai gồm ~n~ số nguyên dương không lớn hơn ~n~ là các số ~a_1, a_2, \cdots, a_n~.

Dòng thứ ba gồm một số nguyên dương ~q~ là số truy vấn ~(1 \leq q \leq 2\cdot10^5)~.

Dòng thứ tư gồm ~q~ số nguyên dương không lớn hơn ~n~, tương ứng với ~q~ truy vấn.

Output

In ra ~1~ dòng gồm ~q~ số nguyên dương là đáp án tương ứng của ~q~ truy vấn.

Simple Input

6
3 2 4 1 6 6
2
1 5

Simple Output

-1 2

Giải thích

Với query số ~1~, quá trình biến đổi là: ~1 \to 3 \to 4 \to 1 \to \cdots~

Với query số ~2~, quá trình biến đổi là: ~5 \to 6 \to 6 \to \cdots~

Phú là một học sinh giỏi trong lớp. Sắp tới, Phú phải thi để nhận chứng chỉ cho ~M~ môn học trong vòng ~N~ ngày. Mỗi môn học được đánh số từ ~1~ đến ~M~ và để nhận được chứng chỉ thứ ~i~ thì cần bỏ ra ~t_i~ ngày để ôn tập và các ngày ôn tập không cần liên tiếp. Một ngày Phú có thể tham gia thi, ôn tập hoặc nghỉ ngơi.

Bạn được biết lịch tổ chức các kì thi của ~M~ môn học sắp tới trong vòng ~N~ ngày. Hãy giúp Phú lên lịch sao cho số ngày cần là ít nhất để có thể lấy được ~M~ chứng chỉ.

Input

Dòng đầu tiên gồm ~2~ số nguyên ~N~, ~M~ ~(1 \leq N, M \leq 10^5)~.

Dòng tiếp theo gồm ~N~ số nguyên ~X_1, X_2, \cdots, X_N~ với ~X_i~ ~(0 \leq X_i \leq M)~ thể hiện cho ngày thứ ~i~ có kì thi để lấy chứng chỉ ~X_i~. Nễu ~X_i = 0~ thì ngày đó không có kì thi nào được tổ chức.

Dòng cuối cùng là ~M~ số nguyên ~t_1, t_2, \cdots, t_M~ với ~t_i~ ~(1 \leq t_i \leq 10^5)~ là số ngày cần ôn tập để lấy được chứng chỉ thứ ~i~.

Output

Gồm ~1~ số duy nhất là số ngày ít nhất để Phú có thể nhận được tất cả các chứng chỉ.

Nếu không thể lấy trong vòng ~N~ ngày thì xuất ~-1~.

Simple Input

9 2
1 1 2 0 1 2 1 1 2
2 1

Simple Output

5

Giải thích

Phú sẽ ôn tập ngày ~1~ cho môn thứ ~2~ và thi nó vào ngày thứ ~3~.

Phú sẽ ôn tập ngày ~2~ và ~4~ cho môn thứ ~1~ và thi nó vào ngày thứ ~5~.

Luna là một người yêu thích toán học đặc biết là các con số liên quan đến lập phương.

Bình thường Luna rất thích thú với các con số nguyên không âm ~X~ và Luna sẽ đi tìm con số ~X^3 = N~ tương ứng, nhưng hôm nay Luna lại muốn hỏi bạn với số nguyên ~N~ thì có số nguyên không âm ~X~ nào thỏa mãn ~N = X^3~ hay không?

Bạn hãy trả lời giúp Luna.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ tương ứng với số lượng bộ test.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên không âm ~N~ với ~(1 \leq N \leq 10^{18})~.

Output

In ra ~T~ dòng, nếu tồn tại số nguyên không âm ~X~ sao cho ~N = X^3~ in ra "YES", ngược lại in ra "NO".

Simple Input

5
2
8
4
27
1000

Simple Output

NO
YES
NO
YES
YES