Bài tập

Vào ngày Quốc tế Thiếu nhi, một đứa trẻ đã đến nhà của Picks và làm rối tung mọi thứ. Picks rất tức giận, bởi nhiều vật quan trọng đã biến mất, trong đó có dãy số yêu thích của anh ấy.

May mắn thay, Picks vẫn nhớ cách khôi phục lại dãy số. Ban đầu, anh ấy tạo ra một mảng số nguyên \(a[1], a[2], \ldots, a[n]\). Sau đó, anh ấy thực hiện \(m\) thao tác trên mảng này. Mỗi thao tác có thể là một trong ba loại sau:

• In tổng: 1 l r --- Picks muốn biết tổng các phần tử trong đoạn từ \(l\) đến \(r\) (tức là \(\sum\limits_{i=l}^{r} a[i]\)).
• Lấy dư: 2 l r x --- Với mỗi \(i\) trong đoạn \([l, r]\), thay \(a[i]\) bằng \(a[i] \bmod x\).
• Gán giá trị: 3 k x --- Gán giá trị \(a[k] := x\).

Bạn hãy giúp Picks thực hiện tất cả các thao tác, và in ra đáp án tương ứng với các thao tác loại 1.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \le n, m \le 10^5)\) --- số phần tử ban đầu và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) --- các phần tử ban đầu của mảng.

• Mỗi dòng trong số \(m\) dòng tiếp theo là một thao tác, theo một trong các định dạng sau:

• 1 $l$ $r$ \((1 \le l \le r \le n)\) --- thao tác loại 1 (in tổng đoạn).

• 2 $l$ $r$ $x$ \((1 \le l \le r \le n, 1 \le x \le 10^9)\) --- thao tác loại 2 (lấy dư đoạn).
• 3 $k$ $x$ \((1 \le k \le n, 1 \le x \le 10^9)\) --- thao tác loại 3 (gán giá trị tại vị trí).

Output

Với mỗi thao tác loại 1, in ra một dòng chứa tổng các phần tử trong đoạn tương ứng. Chú ý: Tổng này có thể vượt quá giới hạn của số nguyên 32-bit.

Example

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

8
5

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

49
15
23
1
9

Scoring

• Có \(30\%\) số điểm có \(n, m \leq 1000\).
• Có \(30\%\) số điểm trong các test không có truy vấn loại \(2\).
• \(40\%\) số điểm không có ràng buộc gì thêm.

Một dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm \(5\) số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

Dòng đầu chứa hai số nguyên dương \(n, k (k < n)\)

Dòng thứ hai chứa n số nguyên \(a_{1}, a_{2},..., a_{n}\) \((|a_{i}| ≤ 10^6)\)

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

5 2
28 9 5 1 69

100

Scoring

\(60\%\) số test có \(n \leq 20\).

\(40\%\) số test còn lại có \(n \leq 10^5\).

Mr. X mới mua một chiếc biệt thự lớn và hiện đại. Biệt thự có thể được biểu diễn bởi một
hình chữ nhật được chia làm \(M\) cột và \(N\) hàng. Các cột được đánh số từ \(1\) tới \(M\) theo chiều
từ trái qua phải (chiều hướng Tây đến Đông). Các hàng được đánh số từ \(1\) tới \(N\) theo chiều
từ dưới lên trên (chiều hướng Nam đến Bắc). Biệt thự có \(M \times N\) phòng, phòng nằm trên cột \(i\) hàng \(j\) được ký hiệu là \((i, j)\). Hai phòng có chung cạnh sẽ có một cửa nối giữa chúng. Ban
đầu, tất cả các cửa nối \(2\) phòng theo hướng Nam-Bắc được mở, các cửa còn lại bị đóng. Đi
qua một cánh cửa mở mất \(1\) phút. Một số căn phòng được đặt công tắc kiểm soát trạng thái
của các cửa. Khi ấn, đè công tắc trong vòng \(1\) phút, mọi cánh cửa đang đóng sẽ mở, và mọi
cánh cửa đang mở sẽ đóng.

Yêu cầu: Xác định thời gian ngắn nhất đi từ phòng \((1, 1)\) tới phòng \((M, N)\).

Input

Dòng đầu tiên chứa 3 số nguyên \(M, N, K\) \((2 \leq M, N \leq 100000, 1 \leq K \leq 200000)\).

\(K\) dòng sau, mỗi dòng gồm \(2\) số nguyên \(x, y\) \((1 \leq x \leq M, 1 \leq y \leq N)\) mô tả phòng \((x, y)\) có đặt công tắc. \(K\) tọa độ phòng là phân biệt.

Output

In ra số phút ít nhất để đi từ phòng \((1, 1)\) tới phòng \((M, N)\). Nếu không đi được, in ra \(-1\).

Example

3 2 1
1 2

4

3 2 1
2 1

-1

Scoring

Subtask \(1\): \(M, N \leq 1000\)

Subtask \(2\): \(K \leq 2000\)

Subtask \(3\): Không có ràng buộc gì thêm

Một tổ chức hoạt động bí mật có \(M\) thành viên. Tổ chức có các nhóm hoạt động được đánh số \(0\), \(1\), \(2\), ..., và trong mỗi nhóm có các nhiệm vụ khác nhau đánh số \(1\), \(2\), \(3\), ... Người đứng đầu tổ chức cần lập mã định danh cho các thành viên trong tổ chức, mỗi thành viên tương ứng với một mã. Mã định danh của một thành viên thuộc nhóm \(n\) và làm nhiệm vụ \(k\) sẽ là số dư của giá trị của hàm \(f(n, k)\) khi chia cho \(10^9 + 7\), với hàm \(f(n, k)\) được định nghĩa như sau :

\(f(n, k) = 1\) nếu \(n = 0\).

\(F(n, k) = \frac{k \times (F(0, k) + F(1,k) + ... + f(n - 1, k))}{n}\), nếu \(n \geq 1.\)

Yêu cầu: Cho danh sách các thành viên, mỗi thành viên cho biết họ hoạt động trong nhóm nào và thực hiện nhiệm vụ gì, hãy xác định mã định danh của \(M\) thành viên của tổ chức đó.

Input

• Dòng đầu tiên chứa số nguyên \(M\) (\(1 \leq M \leq 2 \times 10^5\)).

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, k\) cách nhau bởi dấu cách (\(1 \leq i, k \leq 2 \times 10^5\)) thể hiện mỗi thành viên hoạt động với mã nhóm \(i\) và thực hiện nhiệm vụ thứ \(k\).

Output

Gồm \(M\) dòng, mỗi dòng chứa một số nguyên là mã định danh của một thành viên, theo đúng thứ tự trong danh sách đã cho ở tệp đầu vào.

Example

4
1 13
2 213
5 45
7 56789

13
22791
1906884
460782414

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n \leq 3\), \(k \leq 2.10^5\);
• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n + k \leq 65\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : \(M \leq 5.10^3\), \(n, k \leq 5.10^3\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : không có ràng buộc gì thêm.