VÙNG QUÉT CỦA ROBOT

Cho một bảng số gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m, từ trên xuống dưới; các cột được đánh số từ 1 đến n, từ trái sang phải.

Ô nằm ở dòng i, cột j được gọi là ô (i, j) và có giá trị bằng:

i × j

Có q lượt quét độc lập. Trong mỗi lượt, một robot được đặt tại ô (x, y) và có bán kính quét k. Robot quét tất cả các ô (i, j) thỏa mãn đồng thời hai điều kiện:

|i - x| ≤ k
|j - y| ≤ k

Vùng quét của robot có dạng hình vuông tâm (x, y). Phần nằm ngoài bảng sẽ bị loại bỏ.

Yêu cầu

Với mỗi lượt quét, hãy tính tổng giá trị của tất cả các ô nằm trong vùng quét của robot.

Các lượt quét độc lập với nhau và không làm thay đổi giá trị của bảng.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên m, n, q — số dòng, số cột của bảng và số lượt quét.
• Trong q dòng tiếp theo, mỗi dòng chứa ba số nguyên x, y, k, mô tả vị trí của robot và bán kính của một lượt quét.

Kết quả

In ra q dòng. Dòng thứ i ghi tổng giá trị của tất cả các ô nằm trong vùng quét của robot ở lượt thứ i.

Ví dụ

Dữ liệu vào

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

Kết quả

54
36
315

Giải thích

Lượt quét thứ nhất

Robot đứng tại ô (2, 3) và có bán kính k = 1. Vùng quét gồm các dòng từ 1 đến 3 và các cột từ 2 đến 4:

Tổng giá trị các ô bằng:

2 + 3 + 4 + 4 + 6 + 8 + 6 + 9 + 12 = 54

Lượt quét thứ hai

Robot đứng tại ô (1, 1) và có bán kính k = 2. Theo bán kính, vùng quét có thể kéo dài từ dòng -1 đến dòng 3 và từ cột -1 đến cột 3. Phần nằm ngoài bảng bị loại bỏ nên vùng quét thực tế gồm các dòng từ 1 đến 3 và các cột từ 1 đến 3. Tổng giá trị các ô bằng 36.

Lượt quét thứ ba

Robot đứng tại ô (4, 5) và có bán kính k = 10. Bán kính đủ lớn để robot quét toàn bộ bảng. Tổng giá trị của toàn bộ bảng bằng:

(1 + 2 + 3 + 4 + 5) × (1 + 2 + 3 + 4 + 5 + 6) = 15 × 21 = 315

Giới hạn

1 ≤ m, n ≤ 60000
1 ≤ q ≤ 200000
1 ≤ x ≤ m
1 ≤ y ≤ n
0 ≤ k ≤ 60000

Subtask 1 — 20% số điểm

m, n ≤ 30
q ≤ 10

Subtask 2 — 20% số điểm

m, n ≤ 1000
q ≤ 1000

Subtask 3 — 20% số điểm

Vùng quét của robot luôn nằm hoàn toàn bên trong bảng.

Subtask 4 — 40% số điểm

Không có giới hạn bổ sung.

NHỮNG VIÊN BI CỦA AN

An có một số viên bi và muốn thực hiện hai công việc khác nhau.

Số túi cần dùng

Mỗi túi chứa tối đa 3 viên bi và các túi không bắt buộc phải đầy.

Với một số tự nhiên dương X, gọi số túi cần dùng của X là số nguyên dương nhỏ nhất a sao cho:

a × 3 ≥ X

Ví dụ:

• Số túi cần dùng của 3 là 1.
• Số túi cần dùng của 4 là 2.
• Số túi cần dùng của 8 là 3.

Số tầng hoàn chỉnh

An dùng các viên bi để xếp thành một tháp:

• Tầng thứ nhất cần 1 viên bi.
• Tầng thứ hai cần 2 viên bi.
• Tầng thứ ba cần 3 viên bi.
• Tầng thứ b cần b viên bi.

Để xây hoàn chỉnh b tầng, An cần:

1 + 2 + 3 + ... + b

viên bi.

Với một số tự nhiên dương X, gọi số tầng hoàn chỉnh của X là số nguyên lớn nhất b sao cho:

1 + 2 + 3 + ... + b ≤ X

Ví dụ:

• Với 5 viên bi, An xây được 2 tầng hoàn chỉnh vì 1 + 2 = 3.
• Với 6 viên bi, An xây được 3 tầng hoàn chỉnh vì 1 + 2 + 3 = 6.
• Với 9 viên bi, An vẫn chỉ xây được 3 tầng hoàn chỉnh.

Cho hai số tự nhiên N và M.

Đặt:

• u là tổng số túi cần dùng của các số tự nhiên dương nhỏ hơn N.
• v là tổng số tầng hoàn chỉnh của các số tự nhiên dương nhỏ hơn M.

Hãy tính u + v.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên N (1 ≤ N ≤ 10^9).
• Dòng thứ hai chứa số nguyên M (1 ≤ M ≤ 10^9).

Dữ liệu ra

In ra một số nguyên là giá trị u + v.

Ví dụ

8
12

40

Giải thích

Các số tự nhiên dương nhỏ hơn 8 là:

1, 2, 3, 4, 5, 6, 7

Số túi cần dùng tương ứng là:

1, 1, 1, 2, 2, 2, 3

Do đó:

u = 1 + 1 + 1 + 2 + 2 + 2 + 3 = 12

Số tầng hoàn chỉnh tương ứng với các số từ 1 đến 11 là:

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

Do đó:

v = 28

Vậy kết quả là:

u + v = 12 + 28 = 40

Trang trí bàn tiệc

Bạn có r quả bóng bay màu đỏ, g quả bóng bay màu xanh lá cây và b quả bóng bay màu xanh dương.

Để trang trí một chiếc bàn cho bữa tiệc, bạn cần dùng đúng ba quả bóng bay. Ba quả bóng được gắn vào cùng một bàn không được có cùng màu, tức là trong ba quả bóng phải có ít nhất hai màu khác nhau.

Biết số lượng bóng bay của mỗi màu, hãy xác định số bàn lớn nhất t có thể được trang trí theo yêu cầu trên.

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên r, g và b (0 ≤ r, g, b ≤ 2 × 10^9) — lần lượt là số quả bóng bay màu đỏ, màu xanh lá cây và màu xanh dương.

Ba số được phân cách bởi đúng một dấu cách.

Dữ liệu ra

In ra một số nguyên t — số bàn lớn nhất có thể được trang trí theo yêu cầu.

Ví dụ 1

Input

5 4 3

Output

4

Ví dụ 2

Input

1 1 1

Output

1

Ví dụ 3

Input

2 3 3

Output

2

Giải thích

Trong ví dụ thứ nhất, ta có thể trang trí bốn bàn bằng các nhóm bóng sau:

rgg, gbb, brr, rrg

Trong đó:

• r biểu diễn bóng bay màu đỏ.
• g biểu diễn bóng bay màu xanh lá cây.
• b biểu diễn bóng bay màu xanh dương.

TÍNH TỔNG CỘT SÓNG ĐÔI

Cho một bảng vuông kích thước N x N. Các số từ 1 đến N^2 được điền lần lượt theo từng hàng và tuân theo quy luật sóng đôi như sau:

• Hai hàng đầu tiên được điền từ trái sang phải.
• Hai hàng tiếp theo được điền từ phải sang trái.
• Hai hàng tiếp theo lại được điền từ trái sang phải.
• Quy luật trên tiếp tục lặp lại cho đến khi điền hết bảng.

Như vậy, hướng điền của các hàng là:

Ô ở hàng 1, cột 1 chứa số 1.

Cho số nguyên X. Hãy tính tổng tất cả các số nằm trên cột X của bảng.

Input

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên N — kích thước của bảng (1 ≤ N ≤ 10^10).
• Dòng thứ hai chứa số nguyên X — chỉ số cột cần tính tổng (1 ≤ X ≤ N).

Output

In ra một số nguyên là tổng tất cả các số nằm trên cột X.

Ví dụ

Input

6
3

Output

110

Giải thích

Với N = 6, Các số nằm trên cột $3$ là:

3, 9, 16, 22, 27, 33

Do đó, tổng cần tìm là:

3 + 9 + 16 + 22 + 27 + 33 = 110

Xáo trộn để tạo xâu đối xứng

Giới hạn thời gian: 2 giây
Giới hạn bộ nhớ: 256 MB

Cho một xâu s chỉ gồm các chữ cái Latin viết thường.

Bạn có thể thực hiện thao tác sau với xâu s: chọn một xâu con liên tiếp của s (xâu con này có thể rỗng) và xáo trộn nó, tức là sắp xếp lại các ký tự trong xâu con theo thứ tự tùy ý.

Nhắc lại rằng xâu đối xứng là xâu có thứ tự các ký tự giống nhau khi đọc từ trái sang phải và từ phải sang trái. Ví dụ, các xâu a, bab, acca, bcabcbacb là các xâu đối xứng, còn các xâu ab, abbbaa, cccb thì không.

Hãy xác định độ dài nhỏ nhất có thể của xâu con cần được xáo trộn để biến xâu s đã cho thành một xâu đối xứng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 10^4) — số lượng bộ test.

Mỗi bộ test gồm một dòng chứa xâu s (2 ≤ |s| ≤ 2 × 10^5), chỉ gồm các chữ cái Latin viết thường.

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

• Độ dài của xâu s là số chẵn.
• Xâu s luôn có thể được biến đổi thành một xâu đối xứng.
• Tổng độ dài của các xâu s trong tất cả các bộ test không vượt quá 2 × 10^5.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên — độ dài nhỏ nhất có thể của xâu con cần được xáo trộn để biến xâu s thành một xâu đối xứng.

Ví dụ

Dữ liệu vào

4
baba
cc
ddaa
acbacddacbca

Dữ liệu ra

2
0
3
2

Giải thích

• Ở bộ test thứ nhất, có thể xáo trộn hai ký tự cuối của baba để thu được baab.
• Ở bộ test thứ hai, xâu đã là xâu đối xứng nên ta có thể chọn một xâu con rỗng. Vì vậy, đáp án là 0.
• Ở bộ test thứ ba, có thể xáo trộn ba ký tự đầu của ddaa để thu được adda.
• Ở bộ test thứ tư, có thể xáo trộn hai ký tự ở vị trí 4 và 5 của acbacddacbca để thu được acbcaddacbca.

Xâu giống nhau

Thầy Thịnh TICA có một xâu s = s1s2...sn và một ký tự c. Anh ấy muốn biến tất cả các ký tự của xâu thành ký tự c bằng số phép biến đổi ít nhất.

Trong một phép biến đổi, Thầy Thịnh chọn một số nguyên x (1 ≤ x ≤ n). Với mọi vị trí i không chia hết cho x, ký tự s[i] được thay bằng ký tự c.

Hãy tìm số phép biến đổi ít nhất cần thực hiện để tất cả các ký tự của xâu đều bằng c, đồng thời in ra các giá trị x được sử dụng trong những phép biến đổi đó.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 10^4) — số lượng bộ test.
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên chứa số nguyên n và một chữ cái Latin thường c (3 ≤ n ≤ 3 × 10^5) — độ dài của xâu s và ký tự mà xâu kết quả phải gồm toàn bộ.
  • Dòng thứ hai chứa xâu s gồm n chữ cái Latin thường — xâu ban đầu.

Tổng giá trị n của tất cả các bộ test không vượt quá 3 × 10^5.

Dữ liệu ra

Với mỗi bộ test:

• Trước tiên, in ra một số nguyên m — số phép biến đổi ít nhất cần thực hiện để tất cả các ký tự của xâu đều bằng c.
• Tiếp theo, in ra m số nguyên x1, x2, ..., xm (1 ≤ xj ≤ n) — các giá trị x cần sử dụng theo đúng thứ tự thực hiện.

Có thể chứng minh rằng với các ràng buộc đã cho, đáp án luôn tồn tại. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án hợp lệ nào.

Ví dụ

Input

3
4 a
aaaa
4 a
baaa
4 b
bzyx

Output

0
1
2
2
2 3

Giải thích

Trong bộ test thứ ba:

1. Chọn x1 = 2. Những vị trí không chia hết cho 2 được thay bằng b:

   bzyx → bzbx
   

2. Chọn x2 = 3. Những vị trí không chia hết cho 3 được thay bằng b:

   bzbx → bbbb
   

Bài toán: Tìm vị trí trong dãy các số lẻ liên tiếp

Cho dãy ký tự 13579111315171921232527… là các chữ số được viết tiếp bởi các số lẻ liên tiếp từ 1 trở đi. Cho trước số tự nhiên N. Tìm giá trị của chữ số ở vị trí thứ N trong dãy ký tự trên.

Ví dụ:

• Chữ số thứ 11 của dãy số là 5 (nằm ở số 15).
• Chữ số thứ 20 của dãy số là 2 (là ký tự trong số 25).

Ví dụ 1:

Input:

11

Output:

5

Ví dụ 2:

Input:

20

Output:

2