Bài tập

Syrjälä, một thành phố sầm uất, đang tổ chức lễ hội lớn nhất trong năm. Tuy nhiên, bạn lại đang ở Metsälä, một vùng đất xa xôi, và cần tìm cách quay về tham dự sự kiện này với chi phí thấp nhất.

Bạn có một tấm "Thẻ Vàng Ưu Đãi", cho phép giảm giá một lần duy nhất trên một chuyến bay bất kỳ. Khi sử dụng thẻ này, giá vé của chuyến bay đó sẽ giảm một nửa (làm tròn xuống số nguyên).

Hãy tìm lộ trình rẻ nhất để quay về Syrjälä từ Metsälä, tận dụng tối đa tấm thẻ ưu đãi của bạn!

Input

Dữ liệu được nhập từ bàn phím với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5)\) --- số lượng thành phố và chuyến bay.
• Thành phố số 1 là Syrjälä (điểm đến).
• Thành phố số n là Metsälä (điểm xuất phát).
• Mỗi trong số \(m\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(c\) \((1 \leq a, b \leq n, 1 \leq c \leq 10^9)\), mô tả một chuyến bay một chiều từ thành phố \(a\) đến thành phố \(b\) với giá vé \(c\).
• Luôn luôn có ít nhất một lộ trình từ Metsälä \((n)\) đến Syrjälä \((1)\).

Output

In một số nguyên duy nhất --- giá của hành trình rẻ nhất có thể đạt được khi sử dụng tối ưu "Thẻ Vàng Ưu Đãi".

Example

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

2

Một thành phố có \(N\) địa điểm chiến lược và \(M\) con đường một chiều giữa các địa điểm. Là thị trưởng của thành phố, bạn sẽ phải bảo vệ an toàn cho \(N\) địa điểm này.

Để có thể bảo vệ cho các địa điểm, bạn phải xây dựng các đồn cảnh sát tại một vài địa điểm. Đồn cảnh sát tại địa điểm \(i\) có thể bảo vệ cho địa điểm \(j\) nếu \(i = j\) hoặc cảnh sát có thể đi tuần tới địa điểm \(j\) từ \(i\) và có thể quay trở lại đồn tại địa điểm \(i\).

Để có thể xây dựng được các đồn cảnh sát cần phải mất chi phí, do địa hình mỗi địa điểm là khác nhau nên chi phí xây dựng đồn cũng có thể khác nhau.

Bạn phải xác định số tiền nhỏ nhất để xây dựng các đồn cảnh sát để có thể bảo vệ được tất cả \(N\) địa điểm, hơn nữa bạn phải đưa ra có bao nhiêu cách xây dựng để đảm bảo chi phí nhỏ nhất đó.

Input

• Dòng \(1\) chứa số nguyên dương \(N\) \((1 \leq N \leq 10^5)\)

• Dòng \(2\) chứa \(N\) số nguyên, trong đó số nguyên thứ \(i\) là chi phí để xây dựng đồn cảnh sát tại địa điểm \(i\) (chi phí $ \leq 10^9$).

• Dòng \(3\) chứa số nguyên \(M\) \((0 \leq M \leq 3 \times 10^5)\)

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\) và \(v\) \((1 \leq u, v \leq n; u \neq v)\) biểu diễn một con đường một chiều nối từ địa điểm \(u\) tới \(v\). Không có nhiều hơn \(1\) con đường nối giữa \(2\) địa điểm.

Output

Một dòng duy nhất chứa hai số, số thứ nhất là chi phí nhỏ nhất để xây dựng các đồn cảnh sát, số thứ hai là số phương án xây dựng mod \(10^9+7\).

Example

5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1

8 2

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử ban đầu. Bạn cần xử lý \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Truy vấn loại 1: dòng có dạng \(1\ x\) --- nghĩa là gán lại \(a_i := a_i \oplus x\) với mọi \(1 \le i \le n\).
• Truy vấn loại 2: dòng có dạng \(2\ k\) --- nghĩa là in ra phần tử lớn thứ \(k\) trong dãy hiện tại (phần tử lớn thứ nhất là lớn nhất).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(Q\) \((1 \le n, Q \le 10^5)\) --- số phần tử ban đầu và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \le a_i < 2^{30})\) --- các phần tử ban đầu của dãy \(A\).

• Mỗi dòng trong \(Q\) dòng tiếp theo chứa một truy vấn theo định dạng:

• \(1\ x\) \((0 \le x < 2^{30})\) --- truy vấn loại 1.

• \(2\ k\) \((1 \le k \le n)\) --- truy vấn loại 2.

Output

• Với mỗi truy vấn loại 2, in ra một dòng chứa số nguyên là phần tử lớn thứ \(k\) hiện tại trong dãy.

Example

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

3
6
6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 20 & \(n, Q \le 1000\)

2 & 30 & \(x \le 200\)

3 & 50 & Không có ràng buộc bổ sung

\hline
\endtabular

Trên hòn đảo hình vòng tròn, có \(n\) chiếc rương báu vật xếp thành một vòng. Mỗi chiếc rương được đánh số từ \(0\) đến \(n - 1\) và chứa một số lượng vàng ban đầu là \(a_0, a_1, \ldots, a_{n-1}\).

Cướp biển Lập trình viên rất quan tâm đến giá trị của kho báu và thường xuyên thực hiện các hành động sau:

• inc(lf, rg, v) --- Thêm \(v\) thỏi vàng vào mỗi chiếc rương từ vị trí \(lf\) đến \(rg\) (tính cả hai đầu).
• rmq(lf, rg) --- Truy xuất thông tin: rương nào có ít vàng nhất trong đoạn từ \(lf\) đến \(rg\)?

Vì các rương được xếp thành vòng tròn, nên đoạn từ \(lf\) đến \(rg\) có thể được hiểu như sau:

• Nếu \(lf \le rg\): đoạn gồm các chỉ số từ \(lf\) đến \(rg\).
• Nếu \(lf > rg\): đoạn gồm các chỉ số từ \(lf\) đến \(n - 1\), rồi tiếp tục từ \(0\) đến \(rg\).

Hãy giúp Lập trình viên thực hiện tuần tự các thao tác, và ghi lại kết quả mỗi lần anh ta truy vấn rmq!

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng rương.
• Dòng thứ hai chứa \(n\) số nguyên \(a_0, a_1, \ldots, a_{n-1}\) \((-10^6 \le a_i \le 10^6)\) --- số lượng vàng ban đầu ở mỗi rương.
• Dòng thứ ba chứa số nguyên \(m\) \((0 \le m \le 2 \cdot 10^5)\) --- số truy vấn.

• \(m\) dòng tiếp theo, mỗi dòng chứa một truy vấn, có thể ở một trong hai dạng:

• lf rg --- Truy vấn loại rmq.

• lf rg v --- Truy vấn loại inc.

Output

Với mỗi truy vấn loại rmq, in ra một dòng chứa số lượng vàng ít nhất trong đoạn được hỏi.

Example

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

1
0
0