Để tạo niềm vui cho mọi người, chính quyền quyết định lắp đặt một thiết bị ở nơi công cộng. Thiết bị này giao tiếp với mọi người thông qua bàn phím và màn hình và có một số nguyên lưu bên trong bộ nhớ của nó. Ban đầu số nguyên này khởi đầu bằng 1.

Thiết bị hoạt động như sau:

• Một người gõ một số nguyên từ bàn phím

• Thiết bị sẽ nhân số trong bộ nhớ của nó với số nguyên vừa gõ và kết quả được lưu lại vào chính bộ nhớ này.

• Thiết bị sẽ hiển thị lời chào lên màn hình nếu như số trong bộ nhớ là số chính phương. Khi đó người gõ số sẽ được nhiều may mắn.

Yêu cầu: Viết chương trình, cho biết dãy số nguyên mà những người chơi lần lượt gõ, xác định xem người chơi nào sẽ là người may mắn.

Dữ liệu: File POTPUNI.INP

• Dòng đầu tiên chứa số nguyên N (1≤N≤500000) là số lượng người tham gia giao tiếp với thiết bị.

• Tiếp theo là N dòng, mỗi dòng ghi một số nguyên được gõ bởi một người theo thứ tự giao tiếp với thiết bị. Các số nguyên này nằm giữa 1 và ~10^6~.

*Chú ý rằng kết quả số trong bộ nhớ có thể vượt quá kiểu số nguyên 64 bit

Kết quả: File POTPUNI.OUT

Output ra kết quả mà mỗi người nhận được theo thứ tự. Ghi "DA" nếu kết quả là số chính phương và "NE" trong trường hợp ngược lại.

Sample Input

7
2
3
6
15
35
21
64

Sample Ouput

NE
NE
DA
NE
NE
DA
DA

Dưới đây là phiên bản đơn giản của một trò chơi phổ biến trong các nơi công cộng ở Bingo. Một cái máy lần lượt đọc các số nguyên và những người chơi sẽ tìm các số nguyên máy vừa đọc trên các tấm thẻ của họ.

Mỗi người chơi có một tấm thẻ được chia thành N hàng, N cột trong mỗi ô được gán một số nguyên trong phạm vi từ 1 đến N2, không có số nào được ghi hai lần.

Khi máy đọc, mỗi người chơi luôn kiểm tra N số cuối cùng máy vừa đọc. Nếu như N số này, theo thứ tự, trùng với 1 hàng của tấm thẻ thì người chơi được 1 điểm.

Ví dụ, giả sử N=3 và người chơi có tấm thẻ sau:

Nếu dãy số máy đọc là 7,1,3,6,4,5,7,1,2,2,8,9,3 thì người chơi được 2 điểm bởi vì hai dãy 6,4,5 và 2,8,9 xuất hiện như là 1 hàng trên thẻ của anh ta.

Yêu cầu:

Mirko muốn biết với cùng một dãy số mà máy đã đọc, số điểm lớn nhất của một tấm thẻ là bao nhiêu?

Dữ liệu: File BINGO.INP

• Dòng đầu tiên ghi hai số nguyên N, B (2 ≤ 𝑁 ≤ 4, 1 ≤ 𝐵 ≤ 10000) là kích cỡ của thẻ và số lượng các số mà máy đọc.

• B dòng tiếp theo mỗi dòng chứa một số theo thứ tự là dãy số mà máy đọc. Tất cả các số này nằm trong phạm vi từ 1 đến N2.

Kết quả: File BINGO.OUT

Một số nguyên là số điểm lớn nhất nhận được

Sample Input

2 11
1
2
1
2
1
2
1
2
3
4
1

Sample Output

5

Một ma trận vuông kích thước N x N được điền đầy bởi các số nguyên từ 1 đến ~N^2~ theo đường zig-zag. Ví dụ, với N=6 ta có ma trận dưới đây:

Có một robot đứng tại ô chứa số 1. Robot này có thể chuyển động theo 4 hướng (trên, dưới, trái, phải) đến ô khác chung cạnh nếu như ô này tồn tại.

Yêu cầu:

Cho dãy K lần chuyển động của robot. Viết chương trình xác định tổng của các số trong các ô mà robot đi qua (nếu một ô đi qua nhiều lần thì số trong ô này được cộng nhiều lần vào tổng)

Dữ liệu: File MATRIX.INP

• Dòng đầu tiên chứa hai số ngyên dương N và K (1≤N≤100000, 1≤K≤ 300000) lần lượt là kích thước của ma trận và số bước chuyển động của robot.

• Dòng thứ hai là dãy K ký tự 'U', 'D','L',R' mô tả các bước chuyển động ('U' - lên trên, 'D' - xuống dưới,'L' -sang trái,'R'-sang phải). Biết rằng với các hướng chuyển động này, robot không ra khỏi ma trận tại bất kỳ một bước nào.

Dữ liệu: File MATRIX.OUT

Một số nguyên dương là tổng các số trong các ô mà robot đi qua. Kết quả đảm bảo luôn là số nguyên 32 bit.

Sample Input 1

6 8
DDRRUULL

Sample Output 1

47

Sample Input 2

3 8
DDRRUULL

Sample Output 2

41

Sample Input 3

6 10
RRRRRDDDDD

Sample Output 3

203