Cho hai số nguyên dương ~x, \; k~.

Tìm số nguyên dương ~y~ bé nhất sao cho ~x \times y~ chia hết cho ~k~.

Input:

• Gồm một dòng duy nhất ghi ~2~ số nguyên ~x, \; k~.

Output:

• Gồm một số nguyên dương là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(50\%)~: ~ x, \; y \leq 10^6~.
• Subtask ~2~ ~(50\%)~: ~ x, \; y \leq 10^{18}~.

Sample Input 1

5 2

Sample Output 1

2

Cho dãy số ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy con liên tiếp của dãy ~A~, mỗi dãy gồm đúng ~K~ phần tử (hai dãy không giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~;
• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output:

• In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.

Scoring:

• Subtask ~1~ ~(60\%)~: ~ N \le 100~;
• Subtask ~2~ ~(20\%)~: ~ N \le 10^3 ~;
• Subtask ~3~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

5 2
1 3 2 1 8

Sample Output 1

5

Cho dãy số nguyên dương ~A~ có ~N~ phần tử và một số nguyên không âm ~K~ cho trước. Một dãy số chẵn lẻ đẹp của dãy ~A~ là dãy con liên tiếp thoả mãn:

• Có ít nhất một số chẵn và ít nhất một số lẻ trong dãy con;
• Gọi ~x~ là tổng các số chẵn, ~y~ là tổng các số lẻ trong dãy con thì ~0 \le x - y \le K~ Đếm số lượng các dãy số chẵn lẻ đẹp của dãy ~A~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~;
• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output:

• In ra một số nguyên dương là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(40\%)~: ~ N \le 200; K \le 10^6 ~;
• Subtask ~2~ ~(30\%)~: ~ N \le 2000; K \le 10^6 ~;
• Subtask ~3~ ~(20\%)~: ~ N \le 2*10^5; K = 0 ~;
• Subtask ~4~ ~(10\%)~: ~ N \le 2*10^5; K \le 100 ~;

Sample Input 1

5 5
1 3 2 9 10

Sample Output 1

3

Sample Input 2

3 1
1 3 1

Sample Output 2

0

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Sau khi đi du học ở Singapore, Quân đã học thêm chuyên ngành phụ về hội hoạ. Cậu đang chuẩn bị hoàn thành tác phẩm đầu tay của mình. Tác phẩm của cậu là một dải ruy băng dài ~n~ ô vuông được đánh số từ ~1~ tới ~n~. Cậu có ~m~ màu sắc khác nhau có thể tô vào dải ruy băng này.

Khi học xong môn hội hoạ, Quân đã có con mắt thẩm mĩ tốt hơn nên cậu biết rằng tác phẩm này được coi là đẹp nếu nó thoả mãn tất cả ~q~ điều kiện có dạng sau:

• ~l \ r ~: Trong đoạn ~[l, r]~ có ít nhất một ô không được tô màu.

Tuy nhiên, Quân chỉ có đủ tiền để mua một tấm ruy băng secondhand giá rẻ nên có một vài ô vuông đã được người chủ cũ tô vào từ trước. Điều này càng khiến cho Quân khó tạo ra được một tác phẩm đẹp hơn.

Hãy giúp Quân tính xem, có bao nhiêu cách tô màu tấm ruy băng này để tạo ra một tác phẩm đẹp. Hai cách tô màu được coi là khác nhau nếu có ô được tô màu ở một cách nhưng không được tô ở cách còn lại, hoặc có ô được tô bằng một màu ở một cách nhưng được tô bằng một màu khác ở cách còn lại.

In ra phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.

Input: Đọc vào từ file ARTISTIC.INP

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, q~ ~(1 \le n, m, q \le 3 \cdot 10^6)~.
• Dòng thứ hai gồm một xâu nhị phân độ dài ~n~ mô tả tấm ruy băng. Ô được đánh số ~1~ là ô đã được tô màu từ trước, ô được đánh số ~0~ là ô được phép tô màu vào.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~ mô tả điều kiện thứ ~i~.

Output: In ra file ARTISTIC.OUT

• In ra một số nguyên không âm là kết quả của bài toán.

Scoring

• Subtask ~1~ (~15\%~ số điểm): ~n, q \le 20~; ~m = 1~.
• Subtask ~2~ (~15\%~ số điểm): ~n, q, m \le 3 \cdot 10^5 ~; ~r_1 < l_2, r_2 < l_3, \ldots, r_{q-1} < l_q~.
• Subtask ~3~ (~30\%~ số điểm): ~n, q, m \le 10^3~.
• Subtask ~4~ (~20\%~ số điểm): ~n, q, m \le 3 \cdot 10^5~.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

7 1 3
0100001
1 2
3 5
4 6

Sample Output 1

13