2025.03.08

Nhập vào số nguyên dương \(n\). Hãy tính tổng các ước của \(n\).

Input

• Số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

• Một số nguyên là tổng các ước của \(n\).

Example

6

12

7

8

Cho 2 dãy số dài \(n\). Kiểm tra xem 2 dãy này có giống nhau không

Input

• Dòng 1: số \(n\) \((3 \leq n < 10^5)\)
• Dòng 2: chứa \(n\) số nguyên \(a_i\) mô tả dãy số \(a(1 \leq a_i \leq 10^9)\)
• Dòng 3: chứa \(n\) số nguyên \(b_i\) mô tả dãy số \(b(1 \leq b_i \leq 10^9)\)

Output

• In ra YES nếu 2 dãy giống nhau, NO nếu 2 dãy không giống nhau

Example

5
2 1 3 5 4
1 2 3 4 5

YES

An đang phải biên tập lại một câu văn. Nhưng câu văn này lạ lắm, mỗi từ cách nhau nhiều hơn một dấu cách, mà chữ cái đầu câu lại còn không viết hoa. An mới nhìn thôi đã nản rồi, bạn hãy giúp An xóa hết những dấu cách thừa giữa các từ, đầu câu, cuối câu và viết hoa chữ cái đầu nhé.

Input

• Gồm một dòng duy nhất chứa xâu \(s\) (\(1 \leq |s| \leq 225)\) là câu văn trước khi sửa, chỉ bao gồm các chữ cái in thường hoặc dấu cách.

Output

• Gồm một dòng duy nhất chứa xâu \(s\) sau khi chuẩn hóa.

Example

 this is an  example

This is an example

Nhập vào số nguyên dương \(N\). In ra xâu fibonacci thứ \(N\) biết:

\(F_1 = A\)

\(F_2 = B\)

\(F_N = F_{N - 1} + F_{N - 2}\)

Input

• Nhập vào số nguyên dương \(N\) (\(1 \leq N \leq 30\)).

Output

• In ra xâu fibonacci thứ \(N\).

Example

3

BA

Cho một mê cung không tường hình chữ nhật có diện tích \(n*m\), trên mỗi ô vuông 1*1 của mê cung đều có đánh một con số thể hiện giá trị của rương kho báu trong ô đó, nhà thám hiểm Dũng là một người biết cách chọn những rương kho báu xịn nhất để mang về. Nhưng do mới vừa đập đá về nên nhà thám hiểm của chúng ta lại chỉ muốn lấy những rương có giá trị bằng giá trị lớn nhất trong các ô trong mê cung, hãy giúp nhà thám hiểm nhé!

Input

• Dòng đầu tiên ghi 2 số \(n\) và \(m\) \((1 \leq n, m \leq 1000)\).
• \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) số nguyên cách nhau bởi dấu cách. \((|a[i,j]| \leq 1000)\)

Output

• In ra số lần xuất hiện trong mảng của phần tử lớn nhất

Example

2 3
1 1 9
8 2 9

2

Cho một hình chữ nhật có \(N\) hàng và \(M\) cột có số thứ tự được đánh từ trên xuống và từ trái sang phải.

Trên mỗi ô có viết một số nguyên và nhiệm vụ chúng ta phải trả lời \(Q\) truy vấn. Mỗi truy vấn sẽ gồm bốn số nguyên là \(x_1, y_1, x_2, y_2\), sẽ mô tả một khu vực con trong hình chữ nhật. Ứng với mỗi truy vấn, hãy in ra tổng của của khu vực con đó, có điểm \((x_1, y_1)\) là ô góc trái trên và có điểm \((x_2, y_2)\) là ô ở góc phải dưới của khu vực.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) (chiều rộng) và \(M\) (chiều dài) \((1 \leq N, M \leq 1000)\)
• \(N\) dòng sau, mỗi dòng chứa \(M\) số nguyên, giá trị tuyệt đối của mỗi số nguyên này không vượt quá \(10^9\)
• Dòng kế tiếp, chứa một số nguyên \(Q\) (số truy vấn) \((1 \leq Q \leq 10^5)\)
• \(Q\) dòng kết tiếp, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\). \((1 \leq x_1 \leq x_2 \leq N)\), \((1 \leq y_1 \leq y_2 \leq M)\)

Output

• In ra \(Q\) dòng, ứng với truy vấn thứ \(i\), in ra một số nguyên là tổng của khu vực hình chữ nhật được nhắc đến bởi truy vấn thứ \(i\).

Example

Test 1

Input

3 3
1 2 3
-4 -5 -6
7 8 9
4
1 1 2 3
2 3 3 3
1 1 2 2
1 1 1 3

Output

-9
3
-6
6

Note