Để 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

Có N con châu chấu đứng xếp thành một hàng chờ xem một buổi biểu diễn. Việc xếp hàng chờ đợi thật là buồn chán nên chúng thực hiện một số bước nhảy cho đỡ buồn có dạng như sau:

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía trái

• Con châu chấu ở vị trí A nhảy qua đầu B con châu chấu khác về phía phải

Tất nhiên các con châu chấu không có cùng độ cao, do vậy khi nhảy con châu chấu phải hết sức cẩn thận để chân của nó không va phải con châu chấu khác. Chính xác hơn nó cần phải nhảy với độ cao ít nhất bằng chiều cao con châu chấu cao nhất cần phải nhảy qua. Cho dãy các bước nhảy theo trình tự, hãy xác định chiều cao tối thiểu mỗi bước nhảy.

Dữ liệu: File NOGA.INP

• Dòng đầu tiên chứa hai số nguyên N, J (2≤N≤~10^5~, 1≤J≤~10^5~) là số lượng châu chấu và số lượng bước nhảy.

• Dòng thứ hai chứa N số nguyên nhỏ hơn 105 là chiều cao của các con châu chấu ở vị trí ban đầu. Độ cao được liệt kê từ trái qua phải.

• J dòng tiếp theo, mỗi dòng mô tả một cú nhảy theo trình tự nhảy. Với mỗi dòng, đầu tiên là số nguyên A (1≤A≤N) là vị trí của con châu chấu bắt đầu nhảy, tiếp theo là ký tự 'L' hoặc 'D' tùy theo là nhảy sang trái hoặc sang phải và cuối cùng là số nguyên B (1≤B≤N) là số lượng con châu chấu cần phải nhảy qua. Các bước nhảy luôn là hợp lệ (tức là B nhỏ hơn hoặc bằng số lượng con châu chấu ở bên trái (nếu 'L') hoặc bên phải (nếu 'D') của vị trí A)

Kết quả: File NOGA.OUT

Ghi ra J dòng, mỗi dòng là chiều cao tối thiểu của một cú nhảy theo trình tự trong file input.

Sample Input

9 3
5 3 8 4 9 3 7 4 2
2 D 3
8 L 2
5 D 2

Sample Output

9
7
4

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

Có một con đom đóm Nhật Bản bay vào một cái hang có đầy chướng ngại vật: măng đá (mọc từ dưới sàn lên), nhũ đá (thả từ trên trần xuống). Hang có độ dài là N đơn vị (ở đây N là số chẵn) và H đơn vị chiều cao. Vật cản đầu tiên luôn là măng đá, sau đó đến nhũ đá, sau đó đến măng đá...Dưới đây là ví dụ về hang có chiều dài 14 và chiều cao 5:

Con đom đóm Nhật Bản vốn học được võ Kung-fu của người Nhật nên nó không bay vòng qua các chướng ngại vật. Đơn giản, nó chọn một độ cao nào đó (là một số nguyên) và bay thẳng từ đầu đến cuối hang. Trên đường bay, nếu gặp chướng ngại vật nào nó sẽ dùng võ kung-fu của mình phá hủy chướng ngại vật này. Trong hình vẽ trên, nếu chọn độ cao 4 thì con đom đóm phải phá hủy 8 chướng ngại vật:

Đây không phải là phương án tốt nhất vì nếu chọn độ cao 1 hoặc 5 số lượng chướng ngại vật cần phá hủy sẽ ít hơn. Hãy xác định số lượng ít nhất các chướng ngại vật cần phá hủy trên đường bay của con đom đóm.

Dữ liệu: File BUBA.INP

• Dòng đầu tiên chứa hai số nguyên N, H (2≤N≤200000, 2≤H≤500000)

• N dòng tiếp theo, mỗi dòng ghi một số nguyên là kích cỡ của chướng ngại vật. Các số nguyên dương này nhỏ hơn H

Kết quả: File BUBA.OUT

Ghi hai số nguyên cách nhau bởi khoảng trống. Số thứ nhất là số lượng nhỏ nhất các chướng ngại vật cần phá hủy và số thứ hai là số cách bay để đạt được điều này.

Sample Input

6 7
1
5
3
3
5
1

Sample Output

2 3