🍎Apple Contest #01

Một hôm PhuocThien đi đến Pháp và được thấy tháp Eiffel vì nó quá đẹp nên PhuocThien đã nghĩ ra một bài toán về Tháp này.

Định nghĩa một ma trận \(N \times N\) được gọi là ma trận Eiffel thì nó phải đáp ứng các điều kiện:

• Tổng của hàng thứ \(1\) và hàng thứ \(N\) bằng nhau; đồng thời nếu cộng hai tổng đó lại với nhau rồi nhân với \(2\) thì kết quả là một số chính phương.
• Tổng của cột thứ \(1\) và cột thứ \(N\) khác nhau; đồng thời nếu cộng hai tổng đó lại với nhau thì kết quả là một số nguyên tố.
• Nếu \(N\) là số chẵn thì kiểm tra thêm:
  • Tích của tổng cột thứ \(N/2\) và tổng hàng thứ \(N/2\) là một số chính phương.
  • Tổng của hai đường chéo khác nhau.
• Nếu \(N\) là số lẻ thì kiểm tra thêm:
  • Tổng của cột thứ \((N+1)/2\) và hàng thứ \((N+1)/2\) là một số nguyên tố.
  • Tổng của hai đường chéo bằng nhau.

Input

• Dòng \(1\): Số nguyên dương \(N\) \((3 \le N \le 15)\).
• \(N\) dòng tiếp theo, Mỗi dòng gồm \(N\) số nguyên cách nhau bởi dấu cách.\((1 \le a[i, j] \le 100)\)

Output

• Nếu là ma trận Eiffel thì in ra Yes ngược lại thì in ra No.

Example

3
2 1 2
1 2 1
2 1 2

No

3
1 2 1
4 1 3
1 2 1

Yes

PhuocThien là một người rất thích số nguyên tố.
hôm nay PhuocThien nghĩ ra \(1\) định nghĩa về số nguyên tố BEST.
Một số nguyên tố \(N\) được gọi là số nguyên tố BEST nếu nó thỏa mản 2 điều kiện:

• Tổng chữ số của \(N\) là chẵn.
• Và nếu đảo tất cả chữ số của \(N\) thì cũng là số nguyên tố.

Input

• Dòng đầu chứa số nguyên dương \(Q\) là số lượng truy vấn \((1 \le Q \le 10^5)\)
• \(Q\) dòng chứa các số nguyên dương \(N\) của các truy vấn \((1 \le N \le 10^6)\)

Output

• Với mỗi truy vấn kiểm tra xem \(N\) có phải số nguyên tố BEST không nếu phải in ra Yes ngược lại in ra No.

Example

5
5
11
13
17
202

No
Yes
Yes
Yes
No

Scoring

• Subtask \(1\): \(20\%\) \((1 \le Q \le 100)\) và \((1 \le N \le 10^4)\).
• Subtask \(2\): \(30\%\) \((1 \le Q \le 10^4)\) và \((1 \le N \le 10^5)\).
• Subtask \(3\): \(50\%\) Không còn ràng buộc gì thêm.

Một ngày vov đố hbl nếu \(67\) người AC thì vov sẽ làm người yêu của hbl nghe vậy hbl từ lâu đã thích vov nên đã đồng ý ngay \(:\)
Dãy số có Quy luật như sau \(:\)
\(5, 11, 28, 53, 126, 175, 296, 369, 538, 851, 972, 1381, 1694, 1863, 2224, 2825, 3498, 3739, 4508, 5061, ...\)
Hãy AC bài tập để đẩy thuyền vov và hbl nhé mọi người ^^!

Yêu cầu

Tìm số thứ \(N\) của dãy số.

Input

• Số nguyên dương \(N\) \((1 \le N \le 10^7)\)

Output

• Một số nguyên dương là số thứ \(N\) của dãy số .

Example

5

126

10

851

Scoring

• Subtask \(1\): \(20\%\) \((1 \le N \le 100)\).
• Subtask \(2\): \(30\%\) \((1 \le N \le 10^5)\).
• Subtask \(3\): \(50\%\) Không còn ràng buộc gì thêm.

Một con sâu đang đói bụng vô tình đã đi vào \(1\) ma trận thức ăn mà PhuocThien đã tạo ra mỗi thức ăn sẽ giúp con sâu no thêm \(a[i, j]\) đơn vị nhưng có \(2\) điều kiện cần được tuân thủ \(:\)

• Chỉ được đi theo hiệu lệnh của PhuocThien.
• Nếu đi ra ngoài thì con sau được tính là bị loại bỏ.

Hiệu lệnh của PhuocThien được hiểu như sau:

• Nếu PhuocThien nói L nghĩa là đi sang trái.
• Nếu PhuocThien nói R nghĩa là đi sang phải.
• Nếu PhuocThien nói U nghĩa là đi sang lên.
• Nếu PhuocThien nói D nghĩa là đi sang xuống.

Chú thích thêm: Con sâu không ngẫu nhiên đi vào mà phải được PhuocThien đưa đến chỗ đó.

Input

• Dòng \(1\): Số nguyên dương \(N\). \((1 \le N \le 1000)\)
• \(N\) dòng tiếp theo: với mỗi dòng nhập \(N\) sô nguyên dương \(a[i, j]\). \((1 \le a[i, j] \le 10^4)\)
• Dòng thứ \(N+1\) nhập \(Q\) truy vấn. \((1 \le Q \le 1000)\)
• Với mỗi truy vấn nhập xâu \(S\) (hiệu lệnh) và \(x\), \(y\) là tọa thả sâu\((1 \le S \le 100, 1 \le x, y \le N)\)

Output

• Nếu sâu không tuân thủ \(2\) điều kiện thì in ra -1, ngược lại thì in ra tổng giả trị mà sâu đã ăn được.

Example

2
1 2
3 4
2
RDLU
1 1
U
1 1

11
-1

3
1 2 3
4 5 6
7 8 9
3
RRD
1 1
DD
2 2
LL
1 1

12
-1
-1