Cho hai số nguyên dương \(A\) và \(N\), hãy tìm chữ số tận cùng của \(A^N\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(A\) và \(N\) \((1 ≤ A, N ≤ 10^8)\), cách nhau một dấu cách.

Output

• Một số nguyên duy nhất là chữ số tận cùng của \(A^N\).

Example

2 10

4

12 3

8

Scoring

• 60% số điểm ứng với: \(1 ≤ A, N ≤ 9\)
• 20% số điểm ứng với: \(1 ≤ A, N ≤ 15\)
• 20% số điểm còn lại ứng với: \(1 ≤ A, N ≤ 10^8\)

Noko có \(1\) dãy số \(a\) gồm \(n\) phần tử, và như rất nhiều bài toán khác, anh ấy muốn kiểm tra độ đẹp của dãy số đó.

Noko ấy có \(1\) dải màu \(b\) gồm có \(k\) số (\(k \le n\)) và khi áp vào 1 đoạn con của dãy số, anh ấy có thể tính ra được độ đẹp của đoạn con đó.

Giả sử đoạn con được kiểm tra là trong đoạn \([i, i + k - 1]\) với \(i \le n - k + 1\), ta có độ đẹp được tính như sau:

\(Noko(i) = a[i] \times b[1] + a[i + 1] \times b[2] + \ldots + a[i + k - 1] \times b[k]\).

Độ đẹp của dãy số được tính bằng \(\max_{i = 1}^{n - k + 1}Noko(i)\) trong dãy số đó.

Hãy giúp Noko tìm độ đẹp của dãy số với dải màu được cho trước.

Input

• Dòng \(1\) gồm hai số nguyên \(n, k\) \((1 \le n, k \le 2 \times 10^5)\).
• Dòng \(2\) gồm \(n\) số nguyên \(a[1], a[2], \ldots, a[n]\) (\(|a[i]| \le 10^6\)).
• Dòng \(3\) gồm \(k\) số nguyên \(b[1], b[2], \ldots, b[k]\) (\(|b[i]| \le 10^6\)).

Output

Độ đẹp của dãy số.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le k \le n \le 3000, |b[i]| \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le k \le n \le 2 \times 10^5, b[i] = 1\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le k \le n \le 2 \times 10^5, b[i] = i\).

Examples

3 2
3 5 10
6 7

100

2 2
3 4
2 -2

-2

Cho bảng số \(A\) gồm \(M\) dòng và \(N\) cột (được đánh số từ \(1\)) có quy luật như sau:

• Tại ô dòng \(i\), cột \(j\), nếu \(i + j\) là số chẵn thì \(A_{i,j} = (i - 1) \times N + j\)
• Nếu \(i + j\) là số lẻ, thì \(A_{i,j} = 0\)

Yêu cầu: Cho hai số nguyên dương \(M, N\), hãy tính tổng của bảng đó.

Input

• Một dòng duy nhất chứa hai số nguyên dương \(M\) và \(N\) \((1 \leq M, N \leq 10^9)\)

Output

• Một số nguyên là tổng các giá trị của bảng sau khi chia dư cho \(1532023\)

Example

3 4

38

1 0 3 0  
0 6 0 8  
9 0 11 0  

Scoring

• 60% số điểm ứng với: \(1 \leq M, N \leq 500\)
• 20% số điểm ứng với: \(1 \leq M, N \leq 10^5\)
• 20% số điểm còn lại ứng với: \(1 \leq M, N \leq 10^9\)

Vì biết Nhật rất kém về số nguyên tố nên trong kì thi này của trường, thầy Nam đã ra một bài toán hóc búa như sau: “Cho 2 số nguyên dương \(a, b\). Hãy tìm số lượng các số trong khoảng [\(a, b\)] sao cho số lượng ước của chúng là một số nguyên tố”

Không chỉ dừng lại đó, thầy Nam còn đánh đố Nhật bằng cách không chỉ cho một bộ \(a, b\) mà cho những \(T\) bộ số. Nhật rất cần qua kì thi này nên anh ấy nhờ đến các bạn lập trình chương trình để giải bài toán của thầy Nam.

Input:

• Dòng đầu chứa số nguyên dương \(T\) là số bộ test
• \(T\) dòng sau mỗi dòng gồm 2 số nguyên dương \(a, b\)

Output:

• \(T\) dòng, dòng thứ \(i\) là kết quả của bộ test thứ \(i\).

Scoring

• Subtask 1 (20%): \(1≤a,b≤200,T≤100\)
• Subtask 2 (20%): \(1≤a,b≤2000,T≤1000\)
• Subtask 3 (20%): \(1≤a,b≤10^6,T≤1000\)
• Subtask 4 (20%): \(1≤a,b≤10^6,T≤10^5\)
• Subtask 5 (20%): $10^6

Ngày hôm nay, các chiến sĩ thuộc Đại đội 9 đang tập luyện tập hợp đội hình trên thao trường. Thao trường có khuôn viên là một hình chữ nhật gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ trên xuống dưới từ \(1\) tới \(r\) và các cột được đánh số từ trái sang phải từ \(1\) tới \(c\). Giao của hàng \(i\) và cột \(j\) sẽ là ô vuông có tọa độ \((i, j)\). Ta định nghĩa khoảng cách giữa hai ô \((x, y)\) và \((u, v)\) sẽ bằng \(|x - u| + |y - v|\). Hiện tại, trên mỗi ô vuông sẽ có tối đa 1 chiến sĩ đang đứng. Một đội hình sẽ cần có đúng \(k\) chiến sĩ. Khi phát hiệu lệnh tập trung đội hình tại một ô (\(x, y\)) nào đó, \(k\) chiến sĩ có khoảng cách từ ô đang đứng tới ô \((x, y)\) là ngắn nhất sẽ di chuyển tới ô này (tính cả chiến sĩ đang đứng tại ô \((x, y)\) nếu có). Thời gian di chuyển của một chiến sĩ sẽ đúng bằng khoảng cách giữa hai ô.

Yêu cầu: Với mỗi ô \((x, y)\) nằm trong khuôn viên của thao trường, hãy tính tổng thời gian di chuyển của \(k\) chiến sĩ sẽ thực hiện xếp đội hình nếu ta phát hiệu lệnh tập trung tại ô này.

Input

• Dòng đầu tiên chứa ba số nguyên \(r\), \(c\) và \(k\) \((1 \leq r, c \leq 2000, 1 \leq k \leq r \times c)\) lần lượt là số hàng, số cột của khuôn viên thao trường và số lượng chiến sĩ cần để tập hợp đội hình.
• Trong \(r\) dòng tiếp theo, dòng thứ \(i\) chứa \(c\) số nguyên \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, c}\) \((0 \leq a_{i,j} \leq 1)\). Trong đó \(a_{i, j} = 1\) có nghĩa là có một chiến sĩ đứng tại ô (\(i,j\)), ngược lại thì không.
• Dữ liệu đảm bảo số lượng chiến sĩ đang có trên thao trường sẽ không nhỏ hơn \(k\).

Output

• Để giảm kích thước dữ liệu đầu ra, gọi \(ans(x,y)\) là tổng thời gian di chuyển của \(k\) chiến sĩ sẽ thực hiện xếp đội hình nếu ta phát hiệu lệnh tập trung tại ô \((x, y)\), hãy in ra một số duy nhất là \(\sum\limits_{x = 1}^{r}\sum\limits_{y = 1}^{c}ans(x, y)\), hay nói cách khác là tổng tất cả \(ans(x, y)\) với mọi \(1 \leq x \leq r\) và \(1 \leq y \leq c\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(r, c \leq 50\).
• Subtask \(2\) (\(10\%\) số điểm): \(r, c \leq 300, k = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(r, c \leq 300\).
• Subtask \(4\) (\(20\%\) số điểm): \(r, c \leq 1000\).
• Subtask \(5\) (\(10\%\) số điểm): \(k = 1\).
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 2
0 0 1
1 1 0
0 1 0

17

3 2 2
1 1 2
2 1 3

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

114

5 4 4 4 3 4
4 3 2 3 3 4
5 4 3 3 2 4
6 5 4 2 2 2
8 7 5 3 3 3