Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy tính tổng các phần tử trong mảng.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^3)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

15

Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy tính tổng các phần tử ở vị trí chẵn của mảng.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^3)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

9

Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy tính tổng các phần tử ở vị trí lẻ của mảng.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^6)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

6

Cho mảng 2 chiều gồm n*m phần tử số nguyên. Hãy tính tổng các phần tử trong mảng.

INPUT

Dòng đầu tiên là số nguyên ~n~ và ~m~ ~(2 \leq n,m \leq 10^2)~

n dòng tiếp theo chứa m số nguyên ~a_{i,0},a_{i,1},a_{i,2},...,a_{i,m-1} (1 \leq a_i \leq 10^6)~

OUTPUT

đáp án của đề bài

SAMPLE INPUT 1

1 5
1 2 3 4 5

SAMPLE OUTPUT 1

15

SAMPLE INPUT 2

2 2
1 2
3 4

SAMPLE OUTPUT 2

10

Cho mảng 2 chiều gồm n*m phần tử số nguyên. Hãy tính tổng các phần tử ~a_{i,j}~ sao cho i+j là số lẻ trong mảng.

INPUT

Dòng đầu tiên là số nguyên ~n~ và ~m~ ~(1 \leq n,m \leq 10^2)~

n dòng tiếp theo chứa m số nguyên ~a_{i,0},a_{i,1},a_{i,2},...,a_{i,m-1} (1 \leq a_i \leq 10^6)~

OUTPUT

đáp án của đề bài

SAMPLE INPUT 1

1 5
1 2 3 4 5

SAMPLE OUTPUT 1

6

SAMPLE INPUT 2

2 2
1 2
3 4

SAMPLE OUTPUT 2

5

Cho mảng 1 chiều gồm ~n~ phần tử số nguyên. Hãy tính tổng các phần tử trong đoạn từ ~l~ đến ~r~.

INPUT

Dòng đầu tiên lần lượt là 3 số nguyên ~n~ ~l~ ~r~ ~(2 \leq l \leq r \leq n \leq 10^3)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

5 1 3
1 2 3 4 5

SAMPLE OUTPUT 1

9

Cho mảng 1 chiều gồm n phần tử số nguyên. Hãy sắp xếp mảng và in ra màn hình.

INPUT

Dòng đầu tiên là số nguyên ~n (2 \leq n \leq 10^3)~

Dòng tiếp theo chứa n số nguyên ~a_0,a_1,a_2,...,a_{n-1} (1 \leq a_i \leq 10^6)~

OUTPUT

Đáp án của bài toán

SAMPLE INPUT 1

6
2 8 4 2 1 5

SAMPLE OUTPUT 1

1 2 2 4 5 8

Cho một mảng gồm ~n~ số nguyên dương, ~a_0, a_1, ..., a_{n-1}~. Bạn hãy tính tổng những giá trị ở vị trí chẵn và tổng những giá trị ở vị trí lẻ nhé.

Lưu ý: Vị trí của mảng bắt đầu từ ~0~.

Input

Dòng đầu tiên, gồm số nguyên duy nhất ~n~ là số lượng phần tử của mảng.

Dòng thứ hai, gồm ~n~ giá trị ~a_0, a_1, ..., a_{n-1}~ là các phần tử của mảng.

Output

In ra hai giá trị theo thứ tự, tổng giá trị ở vị trí lẻ và tổng giá trị ở vị trí chẵn.

Constraints

~1 \le n \le 10^5~

~1 \le a_i \le 10^4~

Input Sample 1

5
1 2 3 2 1

Output Sample 1

4 5

Input Sample 2

5
1 3 2 2 1

Output Sample 2

5 4

Cho một ma trận (mảng hai chiều), có kích thước ~n~ x ~n~ và số nguyên dương ~k~ là ước của ~n~. Giả sử ~a_{i, j}~ là giá trị tại hàng ~i~ và cột ~j~ của ma trận. Hiện tại dữ liệu của ma trận này đang bị lặp lại nhiều lần làm cho ma trận có kích thước lớn, bạn hãy thu gọn ma trận này nhé. Cụ thể khi chia đều ma trận ban đầu thành các ma trận kích thước ~k~ x ~k~, thì các giá trị có được này giống nhau, ta chỉ cần lưu giá trị này một lần. Hãy xem ví dụ để hiểu thêm nhé.

Input

Dòng đầu tiên, gồm cặp số số nguyên ~n~ và ~k~ là kích thước của ma trận và kích thước của ma trận lặp.

Tiếp theo, gồm ~n~ dòng mỗi dòng gồm ~n~ giá trị ~a_{i, 0}, a_{i, 1}, ..., a_{i, n - 1}~ đại diện cho ~n~ các giá trị thuộc dòng thứ ~i~.

Output

Hãy in ma trận đã được rút gọn của ma trận ban đầu.

Constraints

~1 \le n \le 10^3~

~a_{i, j} \in \{0, 1\}~

Input Sample 1

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Output Sample 1

0

Input Sample 2

6 3
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0

Output Sample 2

0 1
1 0

Input Sample 3

6 2
0 0 1 1 0 0
0 0 1 1 0 0
1 1 1 1 1 1
1 1 1 1 1 1
1 1 0 0 0 0
1 1 0 0 0 0

Output Sample 3

0 1 0
1 1 1
1 0 0

Vì những câu chuyện cổ tích quá dài, AliVu đã yêu cầu mình viết lại ngắn gọn và dễ hiểu. Nhiệm vụ của bạn là viết chương trình kiểm tra xem một mảng số nguyên có phải là mảng đối xứng hay không.

Chú ý: Mảng đối xứng là mảng mà thứ tự các phần tử từ đầu đến cuối giống hệt thứ tự từ cuối về đầu.

Input

• Dòng đầu tiên là một số nguyên ~n~ ~(1 \le n \le 10^3)~ - sô phần tử của mảng.
• Dòng thứ hai chứa n số nguyên ~a_1,a_2,a_3,...,a_n~ ~(1 \le a_i \le 10^3)~ - các phần tử của mảng.

Output

• In YES nếu là mảng đối xứng. Ngược lại, in NO.

Sample Input 1

5
1 2 3 2 1

Sample Output 1

YES

Sample Input 2

4
1 2 3 4

Sample Output 2

NO

Cho một mảng có ~n~ giá trị, ~a_0, a_1, ..., a_{n - 1}~. Mentor Popi muốn các bạn thực hiện tính toán trên mảng này theo quy tắc như sau $$S = a_0 + a_1 - a_2 + a_3 - a_4 + \text{...} \pm a_{n-1}$$ Ví dụ: ~n = 5~, ~a = [1, 2, 3, 4, 5]~ ~\implies S = 1 + 2 - 3 + 4 - 5 = -1~

Input

• Dòng đầu tiên, gồm duy nhất một số nguyên ~n~ là kích thước của mảng.
• Tiếp theo, gồm ~n~ giá trị ~a_0, a_1, ..., a_{n - 1}~ đại diện cho ~n~ các giá trị của mảng.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n \le 10^4~
• ~1 \le a_i \le 10^4~

Input Sample 1

5
1 2 3 4 5

Output Sample 1

-1

Input Sample 2

1
5

Output Sample 2

5

Cho một ma trận (mảng 2 chiều) kích thước ~n~ x ~n~, ~a_{i, j}~ là giá trị tại hàng ~i~ và cột ~j~. Mentor Popi định nghĩa sức mạnh của mảng là tổng các phần tử trong ma trận con có kích thước ~k~ x ~k~ lớn nhất. Với giá trị ~k~ cố định được cho sẵn, bạn hãy tìm sức mạnh của mảng.

Ví dụ: ~n = 3~, ~k = 2~ và ma trận ~a = \begin{bmatrix} 1&2&3\\3&2&1\\2&4&6 \end{bmatrix}~, Ta có các ma trận con kích thước ~2~ x ~2~ là:

• ~\begin{bmatrix} 1&2\\3&2 \end{bmatrix}~, tổng các phần tử là ~8~.

• ~\begin{bmatrix} 2&3\\2&1 \end{bmatrix}~, tổng các phần tử là ~8~.

• ~\begin{bmatrix} 3&2\\2&4 \end{bmatrix}~, tổng các phần tử là ~11~.

• ~\begin{bmatrix} 2&1\\4&6 \end{bmatrix}~, tổng các phần tử là ~13~. Vậy kết quả cho ví dụ này là ~13~.

Input

• Dòng đầu tiên, gồm cặp số nguyên ~n~ và ~k~ là kích thước của ma trận và kích thước ma trận con.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ giá trị ~a_{i, 0}, a_{i, 1}, ..., a_{i, n - 1}~ đại diện cho ~n~ các giá trị của hàng thứ ~i~.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le k \le n \le 50~
• ~1 \le a_i \le 50~

Input Sample 1

3 2
1 2 3
3 2 1
2 4 6

Output Sample 1

13

Input Sample 2

3 3
1 2 3
3 2 1
2 4 6

Output Sample 2

24

Cho một ma trận (mảng 2 chiều) kích thước ~n~ x ~m~, ~a_{i, j}~ là giá trị tại hàng ~i~ và cột ~j~. Mentor Popi muốn biết rằng có bao nhiêu vị trí ~i~, ~j~ sao cho ~a_{i, j}~ là bội của ~i + j~.

Chú ý: Các chỉ số của mảng bắt đầu từ ~1~.

Ví dụ: ~n = 3~, ~m = 3~ và ma trận ~a = \begin{bmatrix} 1&2&3\\3&2&1\\2&4&6 \end{bmatrix}~, Ta có các vị trí thỏa mãn như sau: ~(2, 1)~, ~(3, 3)~. Vậy số lượng vị trí thỏa mãn là ~2~.

Input

• Dòng đầu tiên, gồm cặp số nguyên ~n~ và ~m~ là kích thước của ma trận.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ giá trị ~a_{i, 1}, a_{i, 2}, ..., a_{i, m}~ đại diện cho ~m~ các giá trị của hàng thứ ~i~.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n, m \le 50~
• ~1 \le a_i \le 10^4~

Input Sample 1

3 3
1 2 3
3 2 1
2 4 6

Output Sample 1

2

Input Sample 2

3 3
1 2 3
3 4 1
2 4 6

Output Sample 2

3

Cho một mảng ~a~ gồm ~n~ phần tử số nguyên ~a_0,a_1,...,a_{n-1}~. Yêu cầu viết chương trình thực hiện kiểm tra:

• Nếu tất cả các phần tử trong mảng là số chẵn, in ra Chan.
• Nếu tất cả các phần tử trong mảng là số lẻ, in ra Le.
• Nếu mảng chứa số chẵn và số lẻ, in ra Khong dong nhat.

Input

• Một số nguyên ~n~ ~(2 \le n \le 2 \times 10^{5})~ - số lượng phần tử trong mảng.
• Một dãy gồm ~n~ số nguyên ~a_0,a_1,...,a_{n-1}~ ~(0 \le a_i \le 10^5)~.

Output

• In ra một dòng chữ biểu thị tính chất của mảng.

Sample Input 1

5
1 3 5 7 9

Sample Output 1

Le

Sample Input 2

7
1 4 2 5 1 2 10

Sample Output 2

Khong dong nhat

Cho một dãy số gồm ~n~ phần tử ~a_1,a_2,...a_n~ và ~q~ truy vấn ~l~, ~r~ ~(1 \le l \le r \le n)~. Yêu cầu kiểm tra tổng trong đoạn ~[l;r]~ có phải là số nguyên tố hay không.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^{3})~. Độ dài của mảng và số truy vấn.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...a_n~ ~(1 \le a[i] \le 10^{3})~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l~, ~r~ , tương ứng với truy vấn thứ ~i~. Yêu cầu kiểm tra tổng từ ~[l;r]~ có phải là số nguyên tố hay không?

Output

• In ra ~q~ dòng tương ứng với câu trả lời thứ ~i~. In YES nếu tổng là số nguyên tố, ngược lại in NO.

Sample Input 1

5 4
2 3 1 2 7
2 3
3 4
5 5 
1 3

Sample Output 1

NO
YES
YES
NO

Cho mảng gồm ~n~ số nguyên dương ban đầu đều là ~1~, ví trị trong mảng được đánh số từ ~0~ đến ~n - 1~.

Có số nguyên ~q~ là số lượng truy vấn, mỗi truy vấn có định dạng sau:

• 1 l r x, Tăng giá trị của các phần tử từ ~l~ đến ~r~ lên ~x~ đơn vị.

• 2 l r x, Giảm giá trị của các phần tử từ ~l~ đến ~r~ xuống ~x~ đơn vị, nếu âm sẽ gán lại về ~0~.

• 3 l r, các phần tử có giá trị chẵn từ ~l~ đến ~r~ giảm một nửa.

• 4 l r, Các phần tử có giá trị lẻ từ ~l~ đến ~r~ tăng gấp đôi.

• 5 l3 r3 l4 r4, Thực hiện cùng lúc truy vấn loại 3 với l3 r3 và 4 với l4 r4.

• 6 l1 r1 x1 l2 r2 x2, Thực hiện cùng lúc truy vấn loại 1 với l1 r1 x1 và 2 với l2 r2 x2.

• 7, in ra các giá trị của mảng thời điểm hiện tại.

Đảm bảo kết quả của bài toán vẫn sẽ tính được trong kiểu int64

Input

• Dòng đầu tiên là ~n~ và ~q~ lần lượt là số lượng phần tử trong mảng và số lượng truy vấn.
• ~q~ dòng tiếp theo mỗi dòng là truy vấn theo định dạng đã đề cập ở trên.

Output

• In ra q dòng là kết quả của các truy vấn loại 7.

Constraints

• ~1 \le n, q \leq 10^3~
• ~0 \le x~

Input Sample 1

7 12
1 4 5 7
7
2 3 3 45
7
3 4 6
7
4 0 6
7
5 2 5 5 5
7
6 1 3 43 3 5 21
7

Output Sample 1

1 1 1 1 8 8 1 
1 1 1 0 8 8 1 
1 1 1 0 4 4 1 
2 2 2 0 4 4 2 
2 2 1 0 2 2 2 
2 45 44 22 0 0 2