Số chính phương là số nguyên không âm có thể viết dưới dạng bình phương của một số nguyên (ví dụ: 0, 1, 4, 9, 16, 25, …).

Yêu cầu: Cho số nguyên dương ~n~ (~n \le 10^{9}~). Hãy kiểm tra tổng các chữ số của ~n~ có phải là số chính phương hay không.

INPUT

• Một dòng duy nhất chứa số nguyên dương ~n~.

OUTPUT

• Một dòng duy nhất ghi hai số nguyên a b, cách nhau một dấu cách, trong đó:

  • a = 1 nếu tổng các chữ số của ~n~ là số chính phương; ngược lại a = 0;
  • b là tổng các chữ số của ~n~.

SAMPLE INPUT 1

1339

SAMPLE OUTPUT 1

1 16

SAMPLE INPUT 2

2335

SAMPLE OUTPUT 2

0 13

Nhà bác Tâm có mảnh vườn dạng hình thang cân, có đáy nhỏ ~AB = a~, đáy lớn ~DC = b~ và hai cạnh bên ~AD = BC = c~ ~(c < a < b)~. Ở giữa vườn, bác Tâm làm một bồn hoa hình tròn tâm ~O~ có bán kính bằng ~\dfrac{1}{3}~ độ dài đường cao ~AH~ của hình thang ~\big(r = \dfrac{AH}{3}\big)~.

Yêu cầu: Tính diện tích phần đất còn lại của khu vườn (diện tích hình thang trừ diện tích bồn hoa). Lấy ~\pi = 3.14~.

INPUT

• Một dòng duy nhất chứa ba số thực ~a, b, c~ (các số cách nhau một dấu cách).

OUTPUT

• Một số thực — diện tích phần đất còn lại, làm tròn đến hai chữ số thập phân.

SAMPLE INPUT 1

8 12 6

SAMPLE OUTPUT 1

45.40

Trong một buổi tiệc có ~n~ người tham gia trò chơi, người thứ ~i~ sẽ nhận được một tấm thẻ, trên đó ghi một số nguyên có giá trị ~a_i~ ~(1 \le a_i \le 10^9)~. Kết thúc buổi tiệc, người may mắn sẽ được nhận quà. Người thứ ~i~ được gọi là người may mắn nếu số lượng người có cùng giá trị ~a_i~ ghi trên thẻ là một số nguyên tố.

Yêu cầu: với mỗi vị trí ~i~, hãy cho biết người thứ ~i~ có phải là người may mắn hay không. Nếu phải ghi ra 1, ngược lại ghi ra 0.

INPUT

• Dòng 1: ghi số nguyên dương ~n~ (~n \le 10^6~).
• Dòng 2: ghi ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (các số được ghi cách nhau một dấu cách).

OUTPUT

Gồm ~n~ dòng; dòng thứ ~i~ ghi 1 hoặc 0 tương ứng theo yêu cầu.

SAMPLE INPUT 1

7
5 4 4 3 3 3 3

SAMPLE OUTPUT 2

0
1
1
0
0
0
0

• Người thứ 1: giá trị 5 xuất hiện 1 lần → 1 không phải số nguyên tố → in 0.
• Người thứ 2 và 3: giá trị 4 xuất hiện 2 lần → 2 là số nguyên tố → in 1 cho cả hai vị trí.
• Người thứ 4,5,6,7: giá trị 3 xuất hiện 4 lần → 4 không phải số nguyên tố → in 0 cho cả bốn vị trí.

SUBTASKS

Sau khi đậu vào lớp 10 chuyên Tin, Cường được gia đình tặng một hộp quà. Hộp quà gồm ~n~ món quà, món quà thứ ~i~ có giá trị ~a_i~ (~a_i \le 10^9,\; a_i \ne a_j~ với ~i \ne j~; ~1 \le i \le n~). Nhưng để nhận được hộp quà, Cường phải giải đáp được ~Q~ câu hỏi. Câu hỏi thứ ~k~ (~1 \le k \le Q~) chứa 3 tham số ~x,y,z~:

• Nếu ~x = 0~: Cường cần đưa ra tổng giá trị của ~z~ món quà có giá trị nhỏ nhất trong ~y~ món quà có giá trị nhỏ nhất.
• Nếu ~x = 1~: Cường cần đưa ra tổng giá trị của ~z~ món quà có giá trị lớn nhất trong ~y~ món quà có giá trị nhỏ nhất.

Yêu cầu: Hãy giúp Cường trả lời các câu hỏi trên.

INPUT

• Dòng thứ nhất chứa hai số nguyên dương ~n, Q~ (~1 \le n, Q \le 10^5~);
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~1 \le i \le n~);
• ~Q~ dòng sau, mỗi dòng gồm 3 số nguyên ~x,y,z~ (~0 \le x \le 1;\; 1 \le z \le y \le n~).

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

OUTPUT

Với mỗi câu hỏi in kết quả trên một dòng — một số nguyên là tổng theo yêu cầu của câu hỏi.

SAMPLE INPUT 1

6 3
2 1 3 4 6 5
1 6 2
0 5 3
1 4 2

SAMPLE OUTPUT 1

11
6
7

SUBTASKS