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

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

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