Trại hè Tin học Miền Bắc – Thái Nguyên 07/2023

ĐỀ CHUẨN HÓA THEO ĐỊNH DẠNG DMOJ (1 FILE DUY NHẤT)

---

A. SUMWIX

Description

Cho dãy số nguyên a = a1, a2, …, an.
Trọng số của bộ bốn chỉ số i ≤ j < k ≤ t là:

w(i, j, k, t) = max(ai, ai+1, …, aj) × min(ak, ak+1, …, at)

Hãy tính tổng trọng số của tất cả các bộ bốn chỉ số.

Input

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa n số nguyên a1, a2, …, an (1 ≤ ai ≤ 10^9).

Output

• Ghi một số nguyên là tổng trọng số, lấy modulo 1000000007.

Constraints

• 12% số test: n ≤ 20
• 28% số test: n ≤ 1000
• 60% số test: n ≤ 100000

Example

Input

6
3 1 5 3 2 6

Output

773

---

B. EINV

Description

Cho dãy số nguyên a1, a2, …, an và số nguyên k.
Đếm số cặp (l, r) (1 ≤ l < r ≤ n) sao cho dãy a1, a2, …, al, ar, …, an có không quá k nghịch thế.

Input

• Dòng đầu chứa hai số nguyên n, k.
• Dòng tiếp theo chứa dãy a.

Output

• Ghi một số nguyên là số cặp thỏa mãn.

Constraints

• n ≤ 100000
• 0 ≤ k ≤ 10^18
• 1 ≤ ai ≤ 10^9
• 50% số test: n ≤ 1000

Example

Input

5 2
1 3 2 1 7

Output

6

---

C. EVAL

Description

Cho G là một đồ thị vô hướng liên thông có trọng số.
Ngưỡng chấp nhận của cạnh e là số nguyên lớn nhất x (x ≤ 10^9) sao cho khi thay trọng số của e bằng x (các cạnh khác giữ nguyên), tồn tại một cây khung nhỏ nhất của G chứa e.

Input

• Dòng đầu chứa hai số nguyên n, m.
• m dòng tiếp theo, mỗi dòng chứa một cạnh u v w.

Output

• In ra m dòng, mỗi dòng là ngưỡng chấp nhận của cạnh theo thứ tự đầu vào.

Constraints

• 1 ≤ n ≤ 100000
• n − 1 ≤ m ≤ 1000000
• 0 ≤ w ≤ 10^9
• 50% số test: n ≤ 1000, m ≤ 10000

---

D. WDINO

Description

Có n loài khủng long, mỗi loài có vô hạn cá thể. Mỗi loài có thể ghét một số loài khác. Người quản thú có k viên kẹo.

• Gọi một con khủng long vào chuồng: tốn 1 viên kẹo.
• Gọi ra: không tốn kẹo.
• Chuồng hoạt động theo nguyên tắc stack (vào sau ra trước).
• Chỉ được gọi vào nếu trong chuồng không có loài mà nó ghét.

Hỏi có bao nhiêu cách tổ chức sao cho dùng hết k kẹo và cuối cùng chuồng rỗng.

Input

• Dòng đầu chứa n, k, m.
• m dòng tiếp theo chứa u v (u ghét v).

Output

• Ghi một số nguyên là số cách, lấy modulo 1000000007.

Constraints

• 1 ≤ n ≤ 10
• 1 ≤ k ≤ 100
• 0 ≤ m ≤ n(n−1)

Example

Input

2 2 1
1 2

Output

7

---

E. APOD

Description

Đếm số xâu độ dài n, chỉ chứa các ký tự Latin thường, sao cho không có tiền tố nào là xâu đối xứng có độ dài lớn hơn 1.

Input

• Một số nguyên dương n.

Output

• Ghi số lượng xâu thỏa mãn, lấy modulo 1000000007.

Constraints

• 12% số test: n ≤ 20
• 28% số test: n ≤ 1000
• 60% số test: n ≤ 100000

Example

Input

3

Output

16250

---

F. MTK

Description

Đếm số ma trận nhị phân n dòng m cột sao cho trong mọi cặp cột liên tiếp, số lượng mẫu (0 → 1) không vượt quá k.

Input

• Ba số n, m, k (1 ≤ n, m ≤ 40; 0 ≤ k ≤ n).

Output

• Ghi số ma trận thỏa mãn, lấy modulo 1000000007.

Constraints

• 50% số test: n, m ≤ 20

Example

Input

4 3 2

Output

3680

---

G. ISEQ

Description

Cho hoán vị a của {1, 2, …, n}. Với mỗi i, hãy đếm số j ≠ i sao cho khi xóa aj, độ dài LIS chứa ai bị giảm.

Input

• Dòng đầu chứa n.
• Dòng tiếp theo chứa hoán vị a.

Output

• In ra n số là kết quả tương ứng.

Constraints

• n ≤ 2×10^5
• 50% số test: n ≤ 1000

Example

Input

9
1 2 3 6 5 4 7 8 9

Output

5 5 5 6 6 6 5 5 5

---

J. FIGTREE

Description

Hùng đang vẽ một cây nhị phân. Ban đầu có cây cân bằng gồm 3 đỉnh.

Hai thao tác:

• Copy cây hiện tại.
• Paste cây đã copy vào một nút lá.

Hãy tính số thao tác paste ít nhất để tạo được cây mong muốn.

Input

• Một chuỗi ngoặc mô tả cây nhị phân.

Output

• In ra số thao tác paste ít nhất, hoặc -1 nếu không thể.

Constraints

• Số đỉnh ≤ 100000

Example

Input

((()())(((()())(()()))()))

Output

3

---

K. HAPPY

Description

Có n người sống thành vòng tròn (n lẻ). Ngày thứ t, người i gửi thiệp cho:

• (i + 2^t) mod n
• (i − 2^t mod n + n) mod n

Độ hạnh phúc ngày sau bằng tổng độ hạnh phúc nhận được.

Input

• Dòng đầu chứa n, k.
• Dòng tiếp theo chứa a0, a1, …, a(n−1).

Output

• In ra n số là độ hạnh phúc của từng người sau k ngày, modulo 10^9 + 7.

Example

Input

3 1
1 2 3

Output

5 4 3

---

L. DIAM2

Description

Một mã cây là chuỗi ngoặc đúng:

• () biểu diễn cây một nút.
• (A1A2…Ak) biểu diễn cây có gốc và k cây con.

Hãy tính đường kính của cây (số cạnh lớn nhất giữa hai đỉnh bất kỳ).

Input

• Một dòng chứa mã cây (độ dài ≤ 200000).

Output

• Một số nguyên là đường kính của cây.

Example

Input

((()(())))

Output

3

---

M. ARRAY2

Description

Cho dãy số nguyên a. Được phép thay đổi không quá một phần tử để thu được dãy b. Gọi ck là số giá trị phân biệt trong {b1,…,bk}.

Hãy tìm giá trị S nhỏ nhất có thể.

Input

• Dòng đầu chứa số testcase T.
• Với mỗi testcase:
  • Dòng đầu chứa n.
  • Dòng tiếp theo chứa dãy a.

Output

• Với mỗi testcase, in ra giá trị nhỏ nhất.

Constraints

• Tổng n ≤ 10^6

Example

Input

1
4
1 2 3 4

Output

22

---

N. HAT2

Description

Có n cái mũ khác nhau. Công ty phải trả mũ sao cho không quá m người nhận lại đúng mũ của mình.

Input

• Hai số n, m.

Output

• Số cách trả mũ, modulo 10^9 + 7.

Constraints

• n ≤ 10^6

Example

Input

5 2

Output

109

---

O. STORGE

Description

Cho dãy số nguyên không âm a. Mỗi bước được tăng hoặc giảm một phần tử (không âm). Hãy biến đổi dãy thành dãy không giảm với số bước ít nhất.

Input

• Dòng đầu chứa n.
• Dòng thứ hai chứa dãy a.

Output

• Ghi số bước biến đổi ít nhất.

Constraints

• 1 ≤ n ≤ 5000

Example

Input

5
1 4 2 5 2

Output

5