Xét một dãy số nguyên dương có ~n~ phần tử ~a_1, a_2, ..., a_n~. Giá trị của dãy được tính theo công thức sau:

$$\frac{a_1}{1 ^ 1} + \frac{a_2}{2 ^ 2} + ... + \frac{a_n}{n ^ n}$$

Một phép xoay dãy theo chiều kim đồng hồ ~i~ lần sẽ biến dãy ~a_1, a_2, ..., a_n~ thành ~a_{i + 1}, a_{i + 2}, ..., a_n, a_1, ..., a_i~.

Xét tất cả các phép xoay dãy ~a~ ~0, 1, 2, ..., n - 1~ lần. Với mỗi phép xoay dãy, hãy tính giá trị của dãy thu được sau khi xoay.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Kết quả

• Một dòng duy nhất gồm ~n~ số nguyên là giá trị của dãy sau khi xoay ~0, 1, 2, ..., n - 1~ lần. Các kết quả được làm tròn đến số nguyên gần nhất..

Subtask

Ví dụ

Dữ liệu

3
1 2 3

Kết quả

2 3 3

Giải thích

• Với phép xoay ~0~ lần (giữ nguyên), giá trị của dãy là ~\frac{1}{1} + \frac{2}{4} + \frac{3}{27} \approx 1.611~, làm tròn thành ~2~.
• Với phép xoay ~1~ lần, dãy trở thành ~(2, 3, 1)~ có giá trị là ~\frac{2}{1} + \frac{3}{4} + \frac{1}{27} \approx 2.787~, làm tròn thành ~3~.
• Với phép xoay ~2~ lần, dãy trở thành ~(3, 1, 2)~ có giá trị là ~\frac{3}{1} + \frac{1}{4} + \frac{2}{27} \approx 3.324~, làm tròn thành ~3~.

Ta định nghĩa trọng số của một dãy ~b_1, b_2, ..., b_k~, ký hiệu là ~W(b)~, theo công thức sau:

$$W(b) = (b_1 + b_2 + \dots + b_k) \mod m$$

Xét một dãy số nguyên dương ~a_1, a_2, ..., a_n~. Đếm số dãy con ~b~ có độ dài ~k~ của ~a~ có ~W(b) = x~.

Nhắc lại, một dãy ~b~ được gọi là dãy con của một dãy ~a~ khi và chỉ khi tồn tại một cách xóa một số phần tử của ~a~ và giữ nguyên thứ tự các phần tử còn lại để tạo thành dãy ~b~.

Dữ liệu

• Dòng đầu tiên gồm bốn số nguyên dương ~n, k, m, x~ ~(1 \le n \le 800, 1 \le k \le 6, 0 \le x < m \le 2 \times 10^7)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^9)~.

Kết quả

• Một dòng duy nhất gồm số dãy con thỏa mãn.

Subtask

Ví dụ

Ví dụ 1

Dữ liệu

5 2 2 0
1 2 3 4 5

Kết quả

4

Giải thích

• Các dãy con thỏa mãn là: ~(1, 3), (3, 5), (1, 5), (2, 4)~.

Ví dụ 2

Dữ liệu

5 3 2 1
1 2 3 4 5

Kết quả

4

Cho một cây có ~n~ đỉnh, ~n - 1~ cạnh. Mỗi cạnh nối hai đỉnh ~u_i, v_i~ và có trọng số là ~w_i~. Khoảng cách giữa hai đỉnh trên cây là tổng trọng số các cạnh của đường đi đơn giữa hai đỉnh. Ban đầu có ~k~ đỉnh đặc biệt ~x_1, x_2, ..., x_k~. Bạn cần tính tổng khoảng cách nhỏ nhất từ mỗi đỉnh trên cây đến một trong các đỉnh đặc biệt đó. Có ~q~ truy vấn thay đổi các đỉnh đặc biệt, mỗi truy vấn sẽ xóa ~a~ đỉnh ~y_1, y_2, ..., y_a~ khỏi tập đỉnh, sau đó thêm ~b~ đỉnh ~z_1, z_2, ..., z_b~ vào tập đỉnh. Sau mỗi truy vấn, tính tổng khoảng cách nhỏ nhất từ mỗi đỉnh trên cây đến một trong các đỉnh đặc biệt như trên.

Dữ liệu

• Dòng đầu tiên gồm ba số nguyên ~n, k, q~ ~(1 \le k \le n \le 10^5, 0 \le q \le 400)~.
• Dòng tiếp theo gồm ~k~ số nguyên ~x_1, x_2, ..., x_k~ ~(1 \le x_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~x_i~ đôi một phân biệt.
• ~n - 1~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10000)~.
• Tiếp theo là ~q~ cặp dòng mô tả các truy vấn, mỗi cặp dòng có định dạng như sau:
  • Dòng đầu tiên gồm số nguyên dương ~a~, sau đó là ~a~ số nguyên dương ~y_1, y_2, ..., y_a~ ~(0 \le a \le 200, 1 \le y_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~y_i~ đôi một phân biệt và có trong tập các đỉnh đặc biệt hiện tại.
  • Dòng tiếp theo gồm số nguyên dương ~b~, sau đó là ~b~ số nguyên dương ~z_1, z_2, ..., z_b~ ~(0 \le b \le 200, 1 \le z_i \le n)~. Dữ liệu đầu vào đảm bảo các giá trị ~z_i~ đôi một phân biệt và không có trong tập các đỉnh đặc biệt hiện tại.
• Dữ liệu đầu vào đảm bảo sau mỗi truy vấn thay đổi cây có ít nhất ~1~ đỉnh đặc biệt.

Kết quả

• Dòng đầu tiên gồm một số nguyên là tổng khoảng cách với tập đỉnh đặc biệt ban đầu.
• Tiếp theo là ~q~ dòng, dòng thứ ~i~ là tổng khoảng cách sau truy vấn thay đổi thứ ~i~.

Subtask

Ví dụ

Ví dụ 1

Dữ liệu

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

Kết quả

17
8

Giải thích

Hình minh họa cây ban đầu.

• Có duy nhất đỉnh ~1~ là đỉnh đặc biệt.
• Khoảng cách từ các đỉnh ~1, 2, 3, 4, 5~ đến đỉnh ~1~ lần lượt là ~0, 3, 4, 6, 4~, tổng là ~17~.

Hình minh họa cây sau truy vấn thay đổi.

• Có đỉnh ~1~ và ~2~ là đỉnh đặc biệt.
• Khoảng cách từ các đỉnh ~1, 3~ đến đỉnh ~1~ lần lượt là ~0, 4~.
• Khoảng cách từ các đỉnh ~2, 4, 5~ đến đỉnh ~2~ lần lượt là ~0, 3, 1~.
• Tổng khoảng cách là ~8~.

Đây là bài toán tương tác với máy chấm

Máy tính đang có một hoán vị có ~n~ phần tử ~a_1, a_2, ..., a_n~. Nhiệm vụ của bạn cần phải đoán ra hoán vị đó. Bạn được phép hỏi máy tính các câu hỏi thuộc một trong hai dạng sau:

• Dạng 1 - D x y z: Kiểm tra xem ~|a_x - a_y|~ có chia hết cho ~z~ không. Máy tính sẽ trả về True nếu ~|a_x - a_y|~ chia hết cho ~z~, và False trong trường hợp ngược lại.
• Dạng 2 - C x y: Kiểm tra xem ~a_x~ có bé hơn ~a_y~ hay không. Máy tính sẽ trả về True nếu ~a_x < a_y~ và False trong trường hợp ngược lại.

Bạn được sử dụng thao tác dạng 1 không quá ~40000~ lần và thao tác dạng 2 không quá ~20~ lần để đạt điểm tối đa. Bạn có thể nhận được điểm một phần nếu dùng thao tác loại 2 không quá ~Q~ lần với ~Q > 20~.

Tương tác

• Đầu tiên chương trình của bạn cần nhập vào một số nguyên dương ~n~ ~(1 \le n \le 1000)~.
• Tiếp theo chương trình của bạn được phép tương tác với máy chấm. Chương trình của bạn cần in ra truy vấn cho máy chấm theo một trong ba dạng sau:
  • ~D\ x\ y\ z~ ~(1 \le x, y, z \le n)~: Đặt câu hỏi dạng 1 với bộ số ~(x, y, z)~.
  • ~C\ x\ y~ ~(1 \le x, y \le n)~: Đặt câu hỏi dạng 2 với bộ số ~(x, y)~.
  • ~A\ a_1\ a_2\ ...\ a_n~ ~(1 \le a_i \le n, a_i~ đôi một phân biệt~)~: Đoán hoán vị cần tìm là ~(a_1, a_2, ..., a_n)~.
• Sau khi đặt câu hỏi, chương trình của bạn cần nhập vào một xâu ký tự là True hoặc False là câu trả lời của máy tính. Sau khi thực hiện thao tác đoán, chương trình của bạn cần kết thúc ngay lập tức.

Chấm điểm

Điểm của toàn bộ bài làm là điểm nhỏ nhất trong toàn bộ các test.

Giả sử điểm mỗi test tối đa là ~100~. Bạn sẽ nhận được ~0~ điểm nếu thuộc một trong hai trường hợp sau:

• Bạn đoán sai hoán vị cần tìm.
• Bạn sử dụng một trong hai loại câu hỏi quá ~40000~ lần.

Bạn sẽ nhận được các mốc điểm tương ứng theo bảng điểm dưới đây với mỗi ~Q~.

Subtask

Ví dụ

Trong tương tác mẫu này, bạn sử dụng ~1~ câu hỏi dạng 1 và ~1~ câu hỏi dạng 2. Do đó bạn được ~100~ điểm.

Cho hai dãy số nguyên không âm ~a_1, a_2, ..., a_n~ và ~b_1, b_2, ..., b_m~. Nhiệm vụ của bạn là tạo ra một bảng ~c~ kích thước ~n \times m~, với ô ở hàng ~i~ cột ~j~ có giá trị ~0 \le c_{ij} \le 1~ sao cho bảng có đúng ~a_i~ số 1 ở hàng ~i~ và ~b_j~ số 1 ở cột ~j~. Nếu có nhiều bảng như vậy bạn cần tìm bảng có thứ tự từ điển nhỏ nhất.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên ~T~ là số bộ dữ liệu ~(1 \le T \le 5)~.
• Tiếp theo là ~T~ nhóm dòng, mỗi nhóm dòng có dạng như sau:
  • Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 300)~.
  • Dòng tiếp theo gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le m)~.
  • Dòng tiếp theo gồm ~m~ số nguyên không âm ~b_1, b_2, ..., b_m~ ~(0 \le b_i \le n)~.
  • Dữ liệu đầu vào đảm bảo ~a_1 + a_2 + ... + a_n = b_1 + b_2 + ... + b_m~.

Kết quả

• Với mỗi bộ dữ liệu, in ra:
  • ~-1~ nếu không tồn tại kết quả thỏa mãn.
  • ~n~ dòng, mỗi dòng gồm một xâu nhị phân độ dài ~m~. Ký tự thứ ~j~ ở hàng ~i~ là ~0~ khi và chỉ khi ~c_{ij} = 0~ và bằng ~1~ trong trường hợp ngược lại. Nếu tồn tại nhiều bảng thỏa mãn, in ra bảng có thứ tự từ điển nhỏ nhất (xâu nhị phân được tạo thành bằng cách nối ~n~ xâu như trên lại với nhau có thứ tự từ điển nhỏ nhất).

Subtask

Ví dụ

Dữ liệu

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

Kết quả

00000
00001
11100
01100
00000

Đây là bài toán tương tác với máy chấm

Bạn cần tìm hai số nguyên dương ~u, v~ ~(1 \le u \le v \le n)~. Bạn được phép hỏi máy chấm một số câu hỏi. Với mỗi câu hỏi, bạn được đưa ra một tập ~S~ gồm một số (~k~) tập hợp ~S_1, S_2, ..., S_k~, mỗi tập hợp ~S_i~ gồm một số (~x~) vị trí ~a_{i_1}, a_{i_2}, ..., a_{i_x}~. Máy chấm sẽ trả lời bạn bằng một chuỗi nhị phân cho biết trong tập ~S_i~ có ít nhất một trong hai số ~u~ hoặc ~v~ hay không.

Bạn cần giải quyết bài toán với càng ít lần hỏi và tổng ~k~ trong các lần hỏi càng nhỏ càng tốt. Tổng ~k~ tối đa không được phép vượt quá ~180~. Tuy nhiên, để đạt điểm tối đa, tổng ~k~ trong các lần hỏi của bạn không được phép vượt quá ~20~.

Tương tác

• Đầu tiên, chương trình của bạn cần nhập vào hai số nguyên dương ~n~ và ~\theta~, với ~\theta~ là thứ tự subtask của test hiện tại ~(2 \le n \le 1000, 1 \le \theta \le 4)~.
• Tiếp theo, quy trình hỏi đáp bắt đầu. Chương trình của bạn cần hỏi trước.
  • Với truy vấn hỏi, chương trình của bạn cần in ra output có dạng như sau:
    • Dòng đầu tiên có dạng ~?\ k~.
    • ~k~ dòng tiếp theo, mỗi dòng gồm một xâu nhị phân có độ dài ~n~. Ký tự thứ ~i~ trong dòng thứ ~j~ là 1 khi và chỉ khi trong tập ~S_i~ có chứa số ~j~.
  • Sau mỗi truy vấn hỏi, chương trình của bạn cần nhập vào một xâu nhị phân độ dài ~k~ là câu trả lời của máy chấm. Ký tự thứ ~i~ trong xâu là 1 khi và chỉ khi trong tập ~S_i~ có chứa ~u~ hoặc ~v~ (hoặc cả hai).
  • Với truy vấn trả lời, chương trình của bạn cần in ra output có dạng như sau:
    • Một dòng duy nhất có dạng ~!\ u\ v~ ~(1 \le u \le v \le n)~.
  • Chương trình của bạn cần ngắt ngay khi tổng các giá trị ~k~ trong các truy vấn hỏi vượt quá ~180~.

Lưu ý rằng máy chấm có thể thích nghi theo câu hỏi của bạn, nghĩa là cặp số ~u, v~ bạn cần tìm có thể sẽ không được cố định từ trước.

Chấm điểm

Giả sử điểm tối đa của mỗi test là ~100~. Chương trình của bạn sẽ được ~0~ điểm nếu đoán sai một trong hai số. Gọi ~A~ là số lần bạn thực hiện truy vấn hỏi, ~B~ là tổng ~k~ trong tất cả các truy vấn hỏi. Điểm của bạn sẽ được tính theo công thức:

$$S = \frac{1}{log_2(A + 1)} \times C$$

với công thức tính ~C~ được cho trong bảng sau:

Subtask

Ví dụ

Với quy trình tương tác trên, ta có số lần hỏi là ~A = 2~, tổng các giá trị ~k~ là ~B = 1 + 2 = 3~. Theo bảng trên tính được ~C = 100~. Do đó điểm chương trình nhận được là: $$\frac{1}{log_2(A + 1)} \times C = \frac{1}{log_2(3)} \times 100 \approx 63.09$$

Xét biểu thức sau:

$$\pm 1^K \pm 2^K \pm 3^K \pm ... \pm M^K = C$$

Bạn được cho hai số nguyên ~N, K~. Nhiệm vụ của bạn là tìm một số nguyên dương ~M~ và thay thế các dấu ~\pm~ trong biểu thức trên thành dấu cộng hoặc trừ để giá trị ~|N - C|~ là nhỏ nhất có thể.

Dữ liệu

• Một dòng duy nhất gồm hai số nguyên không âm ~N, K~ ~(0 \le N \le 10^{12}, 1 \le K \le 9)~.

Kết quả

• Một dòng duy nhất gồm một xâu chỉ gồm các ký tự + hoặc - mô tả kết quả bài toán. Ký tự thứ ~i~ trong xâu là + nếu dấu ~\pm~ thứ ~i~ trong biểu thức có thể được thay thành dấu cộng; ký tự thứ ~i~ trong xâu là - trong trường hợp ngược lại. Giới hạn độ dài xâu được cho trong bảng dưới đây:

Chấm điểm

• Giả sử điểm tối đa của một test là ~100~. Gọi ~X = |N - C|~ và ~P = 5 - \frac{K}{2}~. Điểm của bạn sẽ được tính như sau:

Subtask

Ví dụ

Ví dụ 1

Dữ liệu

0 2

Kết quả

++-+--+

Giải thích:

Ta có: $$1^2 + 2^2 - 3^3 + 4^2 - 5^2 - 6^2 + 7^2 = 1 + 4 - 9 + 16 - 25 - 36 + 49 = 0$$

Do đó output được ~100\%~ số điểm.

Ví dụ 2

Dữ liệu

0 2

Kết quả

+

Giải thích:

Ta có ~1^2 = 1~, ~P = 5 - \frac{2}{2} = 4~. Do ~0 < |0 - 1| \le 4~ nên điểm của output được tính theo công thức: $$85 + 15 \times (\frac{4 - |2 - 1|}{4})^4 \approx 89.746$$

Do đó output được ~89.746\%~ số điểm.