Một bàn cờ gồm ~n~ dòng, ~m~ cột, các dòng và các cột được đánh số từ ~1~. Mỗi ô được sơn đen hoặc trắng đan xen nhau (như bàn cờ vua). Ở dòng ~i~, cột ~j~ của bàn cờ được sơn màu đen. Hãy xác định số ô được sơn màu đen.

Input

Dòng duy nhất của input chứa bốn số nguyên ~n, m, i, j~.

Output

In ra số ô được tô đen.

Scoring

• Subtask ~1~ (chiếm ~30\%~) số điểm: ~1 \leq n, m \leq 5000~, ~1 \leq i \leq n~, ~1 \leq j \leq m~.

• Subtask ~2~ (chiếm ~70\%~) số điểm: ~1 \leq n, m \leq 10^6~, ~1 \leq i \leq n~, ~1 \leq j \leq m~.

Sample Input 1

10 10 5 5

Sample Output 1

50

Cho số nguyên dương ~N~, tìm một bộ ba ~(x, y, z)~ (~x, y, z > 1~) sao cho ~x \cdot y \cdot z = N~ và ~z~ là lớn nhất, nếu không có bộ ba nào thì in ra ~-1~ (~1 \leq N \leq 2 \cdot 10^9~)

Input

Dòng duy nhất của input chứa số nguyên ~N~.

Output

In ra ba số nguyên ~x, y, z~ sao cho ~z~ là lớn nhất. Nếu có nhiều bộ ba đều cho ra ~z~ lớn nhất, in ra một bộ ba bất kì. Nếu không có bộ ba nào thì in ra ~-1~.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq N \leq 10^2~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq N \leq 5 \cdot 10^3~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq N \leq 2 \cdot 10^9~.

Sample Input 1

1

Sample Output 1

-1

Sample Input 2

12

Sample Output 2

2 2 3

Notes

Cho mảng ~a~ gồm ~n~ phần tử và một số nguyên ~k~. Tách mảng ~a~ ra thành ~k~ đoạn liên tiếp sao cho mỗi phần tử của mảng ~a~ thuộc đúng một đoạn và không có đoạn nào rỗng. Chi phí của một đoạn liên tiếp là bình phương của tổng các phần tử được chọn, chi phí của cả ~k~ đoạn là chi phí của đoạn lớn nhất. Tìm cách cắt để cực tiểu hóa chi phí.

Input

Dòng đầu tiên gồm hai số nguyên ~n, k~.

Dòng tiếp theo gồm ~n~ số nguyên ~a_1, a_2, \cdots, a_n~.

Output

In ra chi phí cực tiểu.

Scoring

• Subtask ~1~ (chiếm ~20\%~ số điểm): ~1 \leq k \leq n \leq 21~; ~-10^4 \leq a_i \leq 10^4~.

• Subtask ~2~ (chiếm ~30\%~ số điểm): ~1 \leq n \leq 1000~; ~1 \leq k \leq \min(n, 30)~; ~-10^4 \leq a_i \leq 10^4~.

• Subtask ~3~ (chiếm ~50\%~ số điểm): ~1 \leq n \leq 10000~; ~1 \leq k \leq \min(n, 40)~; ~-10^4 \leq a_i \leq 10^4~.

Sample Input 1

7 3
15 20 -4 8 14 -2 -5

Sample Output 1

256

Sample Input 2

7 4
-1 -1 -1 1 -1 -1 -1

Sample Output 2

4

Gọi ~f(N)~ là số cặp ~(a, b)~ sao cho ~a, b~ là ước nguyên dương của ~N~ và ~a \cdot b~ là một số chính phương. Cho ~T~ truy vấn, với mỗi truy vấn, cho hai số nguyên ~L, R~, hãy tính ~f(L) + f(L + 1) + \cdots + f(R)~ modulo ~10^9 + 7~ (~1 \leq T \leq 10^7~; ~1 \leq L \leq R \leq 10^7~).

Input

Dòng đầu tiên chứa số nguyên ~T~.

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ (~L \leq R~) thể hiện một truy vấn.

Output

In ra ~T~ dòng tương ứng đáp án của ~T~ truy vấn.

Scoring

• Subtask ~1~ (chiếm ~30\%~ số điểm): ~1 \leq T \leq 1000~, ~1 \leq L \leq R \leq 100~.

• Subtask ~2~ (chiếm ~40\%~ số điểm): ~1 \leq T \leq 10^5~, ~1 \leq L \leq R \leq 10^6~.

• Subtask ~3~ (chiếm ~30\%~ số điểm): ~1 \leq T \leq 10^5~, ~1 \leq L \leq R \leq 10^7~.

Sample Input 1

1
1 5

Sample Output 1

12

Cho một xâu nhị phân ~s~ có độ dài ~n~ và một số nguyên ~k~. Thực hiện tối đa ~k~ operations hoán đổi hai phần tử liền kề trong xâu sao cho số phần tử kề nhau mà khác nhau được cực đại hóa.

Nói theo một cách khác, ta được phép thực hiện tối đa ~k~ lần operation sau: chọn một vị trí ~i~ ~(1 \leq i \leq n - 1)~, hoán đổi hai kí tự ~s_i~ và ~s_{i + 1}~.

Sau khi thực hiện ~k~ operations, tính số vị trí ~i~ nhiều nhất có thể thỏa mãn ~(1 \leq i \leq n - 1)~ và ~s_i \neq s_{i+1}~.

Input

Dòng đầu tiên chứa hai số nguyên ~2 \leq n \leq 300 , k \leq 10^9~.

Dòng thứ hai chứa một xâu nhị phân độ dài ~n~.

Output

In ra số vị trí thỏa yêu cầu đề bài sau khi thực hiện các operations một cách tối ưu.

Scoring

• Subtask ~1~ (chiếm ~5\%~ số điểm): ~n \leq 3~

• Subtask ~2~ (chiếm ~10\%~ số điểm): ~n \leq 20~

• Subtask ~3~ (chiếm ~85\%~ số điểm): không có ràng buộc gì thêm

Sample Input 1

5 3
01100

Sample Output 1

4

Sample Input 2

10 12
0110101000

Sample Output 2

8

Notes

Ở test ví dụ thứ nhất, có thể hoán đổi hai vị trí ~3~ và ~4~ để nhận được xâu ~01010~.

Ở test ví dụ thứ hai, ta có thể làm như sau

• Hoán đổi vị trí ~3~ và ~4~, nhận được xâu ~0101101000~

• Hoán đổi vị trí ~5~ và ~6~, nhận được xâu ~0101011000~

• Hoán đổi vị trí ~7~ và ~8~, nhận được xâu ~0101010100~