☀️Summer Contest #02 - Chill giữa hè

Với sức nóng hủy diệt của mùa hè khi nhiệt độ ngoài trời đã vượt quá 40°C, ledinhbaonam và uia quyết định tạm gác lại những cuộc tranh luận bất tận về số nguyên tố để đi ăn kem giải nhiệt.

Sau khi gọi hai cây kem khổng lồ và tìm được một chỗ ngồi dưới bóng cây, uia bất ngờ đưa ra một câu đố cho ledinhbaonam:

"Nếu hai chúng ta cùng chọn hai số nguyên tố đặc biệt, liệu có bao nhiêu phân số thú vị có thể được tạo ra?"

Cụ thể, uia chọn hai số nguyên tố \(e\) và \(f\).

Một cặp số nguyên tố \((e, f)\) được xem là hợp lệ nếu thỏa mãn đồng thời các điều kiện sau:

• Hiệu tuyệt đối giữa hai số đúng bằng \(n\): \(|e-f|=n\)

• Tổng của chúng không vượt quá \(s\): \(e+f \le s\)

Từ cặp \((e, f)\), hai người tạo ra phân số:

Tuy nhiên, uia chỉ thích những phân số nằm trong một khoảng nhất định và các giá trị không quá lớn.

Vì vậy phân số được tạo ra phải thỏa mãn:

uia đưa ra các giá trị \(a,b,c,d,n,s\) và thách ledinhbaonam tìm đáp án.

Nhiệm vụ

Hãy đếm số lượng phân số có thể được tạo ra từ các cặp số nguyên tố \((e,f)\) thỏa mãn tất cả các điều kiện trên.

Input

• Dòng đầu tiên chứa bốn số nguyên \(a,b,c,d\). (\(1 \le a,b,c,d \le 10^9\))
• Dòng thứ hai chứa hai số nguyên \(n,s\). (\(1 \le n \le s \le 10^7\))

Dữ liệu đảm bảo:

Output

• In ra một số nguyên duy nhất là số lượng phân số thỏa mãn yêu cầu bài toán.

Example

3 1 1 1
2 20

2

1000000 333333 1000000 666667
1000 10000000

46

Mùa hè năm nay quá nóng, ledinhbaonam và uia quyết định xây một trung tâm hỗ trợ du khách trên quần đảo để tránh việc người dân phải di chuyển quá xa trong thời tiết oi bức.

Quần đảo gồm \(N\) hòn đảo được đánh số từ \(1\) đến \(N\) và nằm thẳng hàng theo đúng thứ tự đánh số.

Trên đảo thứ \(i\) có \(D_i\) người dân sinh sống.

Trung tâm hỗ trợ được xây tại đúng một hòn đảo.

Nếu trung tâm được xây tại đảo \(x\), thì một người dân trên đảo \(i\) được xem là phải di chuyển quá xa nếu:

Toàn bộ \(D_i\) người dân trên đảo đó sẽ bị tính vào số người phải di chuyển quá xa.

Nhiệm vụ

Hãy chọn vị trí xây trung tâm sao cho tổng số người dân phải di chuyển quá xa là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên \(N, K\) \((1 \le N \le 2 \cdot 10^5,\ 0 \le K \le N)\)

• Dòng thứ hai chứa \(N\) số nguyên: \(D_1,D_2,\ldots,D_N\) \((0 \le D_i \le 10^4)\)

Output

• In ra số người dân ít nhất phải di chuyển quá xa.

Example

5 1
1 2 1 3 2

3

8 2
3 1 4 1 5 9 2 6

8

uia lấy ra một cuốn sổ tay cũ và chỉ cho ledinhbaonam một dãy số rất dài:

\(1, 3, 7, 13, 21, 31, 56, 89, 130, 179, 267, 301, 374, 543, 640, 857, 1313, 2419, 4115, 6581, \dots\)

uia khẳng định rằng dãy số này được tạo ra theo một quy luật hoàn toàn xác định.

Để kiểm tra khả năng quan sát của ledinhbaonam, uia đưa ra hai vị trí: \(x\) và \(y\) và yêu cầu tìm:

• Giá trị của phần tử thứ \(x\) trong dãy.
• Giá trị của phần tử thứ \(y\) trong dãy.

Nếu tìm đúng cả hai giá trị, ledinhbaonam sẽ chiến thắng trò chơi.

Ngược lại, uia sẽ là người thắng cuộc.

Hãy giúp ledinhbaonam khám phá quy luật của dãy số và tìm ra hai đáp án cần thiết (MOD \(10\)).

Input

• Dòng đầu chứa số nguyên dương \(x\) (\(1 \le x \le 10^9\))
• Dòng thứ hai chứa số nguyên dương \(y\) (\(1 \le y \le 10^9\))

Output

• In ra hai số nguyên trên cùng một dòng:
  • Phần tử thứ \(x\) của dãy(MOD \(10\))
  • Phần tử thứ \(y\) của dãy(MOD \(10\))

Example

5
8

1 9

204
2128

4 2

Trong một đêm đầy sao, ledinhbaonam muốn chuẩn bị một món quà thật đặc biệt dành cho uia. Cậu tạo ra một khu vườn ánh sáng hình chữ nhật gồm \(m\) hàng và \(n\) cột. Mỗi ô trong khu vườn chứa một viên pha lê phát sáng, viên pha lê ở hàng \(i\), cột \(j\) có độ lung linh là \(a_{i,j}\).

Tuy nhiên, những cơn mưa sao băng liên tục xuất hiện khiến độ lung linh của các viên pha lê thay đổi theo thời gian. Vì vậy, uia muốn thường xuyên tìm kiếm một khu vực hoàn hảo để ngắm sao.

Một hình vuông con kích thước \(k \times k\) được gọi là hài hòa nếu độ chênh lệch giữa viên pha lê sáng nhất và tối nhất trong hình vuông không vượt quá một ngưỡng cho trước \(T\). Nói cách khác, nếu gọi \(\max(S)\) là giá trị lớn nhất và \(\min(S)\) là giá trị nhỏ nhất trong hình vuông thì hình vuông đó hợp lệ khi: \(\max(S)-\min(S)\le T\)

Kích thước khu vực ngắm sao không cố định. Với mỗi thời điểm, uia muốn biết kích thước lớn nhất của một hình vuông hài hòa có thể tồn tại trong khu vườn.

Bạn cần xử lý \(Q\) sự kiện thuộc một trong hai loại sau:

• 1 i j X: thay đổi độ lung linh của viên pha lê tại vị trí \((i,j)\) thành \(X\).
• 2 T: tìm giá trị lớn nhất của \(k\) sao cho tồn tại ít nhất một hình vuông con kích thước \(k \times k\) thỏa mãn điều kiện: \(\max(S)-\min(S)\le T\)

Nếu không tồn tại hình vuông nào thỏa mãn, in ra \(0\).

Input

Dòng đầu tiên chứa ba số nguyên \(m, n, Q\). \((1 \le m \le 4,\ 1 \le n \le 40000,\ 1 \le Q \le 50000)\)

\(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{i,j}\). \((0 \le a_{i,j} \le 10^6)\)

\(Q\) dòng tiếp theo mô tả các sự kiện.

Với sự kiện loại 1 i j X: \(1 \le i \le m,\quad 1 \le j \le n,\quad 0 \le X \le 10^6\)

Với sự kiện loại 2 T: \(0 \le T \le 10^6\)

Output

Với mỗi truy vấn loại 2, in ra trên một dòng giá trị lớn nhất của \(k\) thỏa mãn yêu cầu.

Example

2 5 6
1 2 3 4 5
2 3 4 5 6
2 1
2 2
1 1 3 10
2 1
1 2 3 10
2 0

1
2
1
1

3 6 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
2 0
1 2 3 7
2 0
1 2 3 5
2 0

3
3
3

Trong chuyến dã ngoại mùa hè, ledinhbaonam và uia cùng chơi trò Thật hay thách?

Đến lượt mình, ledinhbaonam đã chọn phương án Thách và uia quyết định đưa ra một bài toán.

Nếu không giải được bài toán này, ledinhbaonam sẽ phải nhận một hình phạt bí mật do uia chuẩn bị sẵn.

uia đưa cho ledinhbaonam một dãy gồm \(N\) số nguyên: \(a_1,a_2,\ldots,a_N\)

Mỗi phần tử còn được gắn với một nhãn: \(t_i \in \{0,1,2\}\)

trong đó:

• \(t_i=0\) nếu phần tử thuộc nhóm A.
• \(t_i=1\) nếu phần tử thuộc nhóm B.
• \(t_i=2\) nếu phần tử thuộc nhóm C.

Một đoạn liên tiếp từ vị trí \(l\) đến vị trí \(r\) được gọi là cân bằng nếu số phần tử thuộc cả ba nhóm trong đoạn bằng nhau.

Nói cách khác: \(\#A=\#B=\#C\) trong đoạn \([l,r]\).

Giá trị của đoạn được định nghĩa là: \(a_l+a_{l+1}+\cdots+a_r\)

uia yêu cầu ledinhbaonam tìm giá trị lớn nhất của một đoạn cân bằng.

Nếu không tồn tại đoạn cân bằng nào, hãy in ra: KHONG

Vì không muốn nhận hình phạt nên ledinhbaonam nhờ các bạn coders giúp đỡ.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 5\cdot10^6\))

• Dòng thứ hai chứa \(N\) số nguyên \(t_1,t_2,\ldots,t_N\)

Trong đó:

• \(t_i=0\) nếu phần tử thứ \(i\) thuộc nhóm A.
• \(t_i=1\) nếu phần tử thứ \(i\) thuộc nhóm B.

• \(t_i=2\) nếu phần tử thứ \(i\) thuộc nhóm C.

• Dòng thứ ba chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\) (\(-10^{15} \le a_i \le 10^{15}\))

Output

• In ra giá trị lớn nhất của một đoạn cân bằng.

• Nếu không tồn tại đoạn cân bằng nào, in ra: KHONG

Example

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

33

5
0 0 1 1 1
2 3 4 5 6

KHONG

Lúc đang chơi Domino thì ledinhbaonam bất ngờ nảy ra một trò chơi mới.

Cậu xếp \(N\) quân Domino thành một hàng dài. Trên mỗi quân Domino có ghi một số nguyên, quân thứ \(i\) mang giá trị \(A_i\).

Sau một lúc quan sát, ledinhbaonam nhận thấy có những đoạn Domino trông rất đẹp. Cậu định nghĩa rằng một đoạn liên tiếp từ vị trí \(l\) đến vị trí \(r\) là một đoạn Domino nếu độ chênh lệch giữa giá trị lớn nhất và nhỏ nhất trong đoạn đúng bằng khoảng cách giữa hai đầu đoạn.

Cụ thể, gọi:

Đoạn \([l,r]\) được gọi là Domino nếu:

Nghe qua thì khá đơn giản, nhưng trò chơi nhanh chóng trở nên thú vị hơn khi ledinhbaonam liên tục thay đổi giá trị trên các quân Domino.

Mỗi khi một quân Domino bị thay đổi, toàn bộ những đoạn Domino trước đó có thể không còn hợp lệ nữa.

Vì vậy uia liên tục đặt ra các câu hỏi:

• Thay đổi giá trị của một quân Domino.
• Đếm xem trong một đoạn bàn chơi cho trước có bao nhiêu đoạn Domino.

Do số lượng câu hỏi khá lớn nên uia đã nhờ npgb và các bạn coders giúp đỡ.

Nhiệm vụ

Bạn cần xử lý \(Q\) truy vấn thuộc một trong hai loại sau:

• 1 p x: Gán \(A_p=x\).
• 2 l r: Đếm số đoạn Domino nằm hoàn toàn bên trong đoạn \([l,r]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\). (\(1 \le N \le 1000\), \(1 \le Q \le 5000\))
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\). (\(1 \le A_i \le 10^{18}\))
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo đúng định dạng đã nêu.

Output

• Với mỗi truy vấn loại 2, in ra trên một dòng duy nhất số lượng đoạn Domino tương ứng.

Example

5 2
3 1 2 5 4
2 1 5
2 2 4

9
4

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

8
6