Cho một dãy xâu ~S~ gồm ~n~ kí tự từ ~1~ đến ~9~. Hãy đếm số lượng cặp ~(i, j)~ ~(1 \le i \le j \le n)~ thỏa mãn các chữ số trong đoạn ~[i, j]~ tạo thành một số nguyên chia hết cho ~2023~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài xâu ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ kí tự của xâu ~S~.

Output

Gồm số nguyên duy nhất là kết quả bài toán.

Sample Test

Input:

10
2427624276

Output:

3

Note

Các cặp ~(i, j)~ thỏa mãn là: ~(1, 5)~ ~(6, 10)~, ~(1, 10)~.

Cho một bảng ~A~ gồm ~n~ hàng và ~m~ cột. Mỗi ô ~A[i][j]~ chứa một số nguyên dương không vượt quá ~k~.

Bạn cần xử lý ~q~ truy vấn thuộc một trong hai loại sau:

• 1 u v x: gán ~A[u][v] = x~.
• 2 u v: tìm khoảng cách lớn nhất giữa một ô có giá trị ~u~ và một ô có giá trị ~v~ trong bảng.

Khoảng cách giữa hai ô ~(x_1, y_1)~ và ~(x_2, y_2)~ được tính bởi:

~ |x_1 - x_2| + |y_1 - y_2| ~

Bảo đảm rằng tại thời điểm xuất hiện truy vấn loại 2 u v, trong bảng luôn tồn tại ít nhất một ô mang giá trị ~u~ và ít nhất một ô mang giá trị ~v~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, k~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên dương mô tả bảng ~A~.
• Dòng tiếp theo chứa số nguyên ~q~.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng:
  • 1 u v x
  • 2 u v

Output

• Với mỗi truy vấn loại 2, in ra khoảng cách lớn nhất tương ứng trên một dòng.

Constraints

• ~1 \le n \times m \le 3 \times 10^5~
• ~1 \le k \le n \times m~
• ~1 \le q \le 2 \times 10^5~
• ~1 \le A[i][j] \le k~
• Với truy vấn loại 1 u v x: ~1 \le u \le n~, ~1 \le v \le m~, ~1 \le x \le k~
• Với truy vấn loại 2 u v: ~1 \le u, v \le k~

Scoring

Sample Input 1

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

Sample Output 1

7

Sample Input 2

4 3 12
8 9 1
3 10 12
2 5 11
4 6 7
7
2 1 6
2 6 9
2 2 11
1 3 3 11
2 5 8
2 8 2
2 2 11

Sample Output 2

4
3
2
3
2
2

Giải thích mẫu 1

• Các ô mang giá trị ~1~ là ~(1,2)~, ~(3,2)~, ~(5,1)~.
• Các ô mang giá trị ~3~ là ~(3,3)~, ~(5,2)~, ~(5,5)~.
• Cặp ô cho khoảng cách lớn nhất là ~(1,2)~ và ~(5,5)~.
• Khoảng cách Manhattan giữa hai ô này là

~~ |1-5| + |2-5| = 7 ~~

nên đáp án là ~7~.

Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có ~m~ hàng và ~n~ cột. Các hàng của bảng được đánh số từ ~1~ tới ~m~ từ trên xuông dưới, các cột của bảng số được đánh số từ ~1~ tới ~n~ từ trái qua phải. Giá trị của số nằm ở hàng ~i~ cột ~j~ được kí hiệu là ~a(i,j)~. Cần thực hiện lần lượt ~Q~ thao tác, thao tác thứ ~t~ ~(1 \le t \le Q)~ được mô tả bằng bộ năm số ~x_t,y_t,u_t,v_t,c_t~, thao tác này sẽ tăng tất cả các phần tử ~a(i,j)~ với mọi ~x_i \le i \le u_t, y_t \le j \le v_t~ lên một lượng là ~c_t~ ~(c_t > 0)~.

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả ~Q~ thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện ~Q~ thao tác. Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện ~Q-1~ thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy ~Q~ thao tác, gọi ~W_t~ là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ ~t~ ~(1 \le t \le Q)~, tính ~Min(\{W_1,W_2,...,W_Q\})~.

Input

• Dòng đầu chứa hai số nguyên dương ~n,m~ .
• ~n~ dòng sau, dòng thứ ~i~ gồm ~n~ số nguyên không âm ~a(i,1), a(i,2), ..., a(i,n)~.
• Dòng tiếp theo chứa số nguyên dương ~Q~.
• Tiếp theo là ~Q~ dòng, dòng thứ ~t~ gồm ~5~ số nguyên dương ~x_t,y_t,u_t,v_t,c_t~.

Điều kiện

• ~1 \le n \times m \le 10^6~
• ~1 \le Q \le 10^6~
• ~a(i,j) \le 10^9~.
• ~c_i \le 10^3~.

Output

Gồm một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.

Ví dụ

Input

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

Output

3

Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử ~A_1, A_2, \ldots, A_N~ và số nguyên dương ~M~ (~M \le N~).

Ta cần xây dựng một dãy số nguyên dương ~B~ gồm đúng ~M~ phần tử.

Với hai dãy số ~S~ và ~T~ cùng độ dài ~M~, định nghĩa độ lệch giữa chúng là:

~F(S, T) = \sum_{i=1}^{M} |S_i - T_i|~

Tức là tổng trị tuyệt đối của hiệu các phần tử tương ứng.

Xét tất cả các đoạn con liên tiếp độ dài ~M~ của dãy ~A~:

• ~A[1...M]~,
• ~A[2...M+1]~,
• ...
• ~A[N-M+1...N]~.

Độ tương thích giữa dãy ~B~ và dãy ~A~ được định nghĩa là:

~G(B) = \sum_{i=1}^{N-M+1} F(A[i...i+M-1], B)~

Yêu cầu:
Hãy tìm giá trị nhỏ nhất có thể của ~G(B)~.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~M \le N \le 3 \times 10^5~);
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ (~A_i \le 2 \times 10^5~ với mọi ~1 \le i \le N~).

Kết quả ghi ra màn hình

• In ra một số nguyên duy nhất là giá trị nhỏ nhất có thể của ~G(B)~.

Ví dụ

Input 1

5 3
3 1 5 2 6

Output 1

12

Giải thích 1: Một dãy ~B~ tối ưu là: ~[3, 2, 5]~.

Input 2

4 2
2 5 8 3

Output 2

11

Ràng buộc:

• Có ~20\%~ số test tương ứng với ~M = 1,\ N \le 1000,\ A_i \le 1000~;
• ~20\%~ số test tương ứng với ~M = 1~;
• ~20\%~ số test tương ứng với ~N \le 1000,\ A_i \le 1000~;
• ~20\%~ số test tương ứng với ~N, M \le 2 \times 10^4,\ A_i \le 1000~;
• ~20\%~ số test còn lại không có ràng buộc bổ sung.

Cho số nguyên dương ~N~ và dãy hoán vị từ ~1~ đến ~N~. Hãy tính tổng chi phí nhỏ nhất để sắp xếp dãy hoán vị ban đầu thành dãy tăng dần. Biết rằng có thể chọn một dãy con liên tiếp từ ~i~ đến ~j~ và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là ~\lfloor \sqrt {j - i + 1} \rfloor~ (lấy phần nguyên, ví dụ ~\lfloor 10,3333 \rfloor = 10~).

Dữ liệu vào từ tệp văn bản SX.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên dương là hoán vị từ ~1~ đến ~N~.

Kết quả ghi ra tệp văn bản SX.OUT:

Chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 9;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 2000;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thoả mãn ~N \leq 10^6.~

Ví dụ

Input

5
3 1 4 2 5

Output

2

Giải thích

Chọn dãy con ~[3, 1]~ mất chi phí ~1~ và chuyển dãy thành ~[1, 3, 4, 2, 5]~, sau đó chọn dãy con ~[3, 4, 2]~ với chi phí ~1~ để sắp xếp thành dãy ~[1, 2, 3, 4, 5]~ với tổng chi phí là ~2~.