Bài tập

Cho dãy số nguyên \(a\) gồm \(n\) số nguyên. Số nghịch thế của \(a\) là số cặp \(i, j\) sao cho \(1 ≤ i < j ≤ n\) và \(a_{i} > a_{j}\) . Ta thực hiện \(Q\) biến đổi trên \(a\), mỗi biến đổi có dạng:

Tăng \(a_{i}\) lên một lượng bằng x.

Yêu cầu in ra sau số nghịch thế của \(a\) sau mỗi truy vấn

Input

• Dòng đầu chứa \(n, Q\)

• Dòng tiếp theo chứa \(n\) số tự nhiên: \(a_{1}, a_{2}, . . . , a_{n}\)

• \(Q\) dòng tiếp theo mỗi dòng chứa \(i, s\). Công thức tính \(x\) là: \(x = |s + sum|\%(2 × 10^9 + 1) − 10^9\). Ở đây sum là tổng các kết quả của các truy vấn trước truy vấn này

Output

Gồm \(Q\) dòng ghi kết quả tương ứng

Example

4
1 2 3 4
2
3 999999998
3 1000000003

1
1

Scoring

\(1 ≤ n, Q ≤ 10^5, 0 ≤ s ≤ 2 × 10^9\), \(−10^9 ≤ a_{i} ≤ 10^9\) trong mọi thời điểm

• \(30\%\) test: \(n, Q ≤ 10^4\)

Đêm Giao thừa năm nay, bác VCB một nghệ nhân pháo hoa lão làng muốn tạo ra màn trình diễn ánh sáng chưa từng có để chào đón năm mới. Bác VCB sở hữu một dây pháo hoa thần kì. Ban đầu, dây pháo hoa chỉ có một đốm sáng khởi nguồn mang năng lượng là \(0\). Quy trình kích hoạt dây pháo diễn ra qua \(Q\) bước, được đánh số từ \(1\) đến \(Q\). Tại bước thứ \(i\), một trong hai sự kiện sau sẽ xảy ra:

• 1 x: Bác VCB chọn một đốm mang năng lượng \(x\) đang có trên dây. Bác gắn thêm một đốm sáng mới mang năng lượng đúng bằng số thứ tự của bước hiện tại \(i\) vào phía sau đốm sáng \(x\).
• 2 x y: Bác VCB chọn hai đốm sáng mốc là \(x\) và \(y\) đang tồn tại trên dây. Tất cả các đốm sáng nằm ở giữa \(x\) và \(y\) sẽ đồng loạt nổ tung, tạo thành chùm sáng rực rỡ và sau đó biến mất vĩnh viễn khỏi dây pháo nhưng hai mốc \(x\) và \(y\) vẫn giữ nguyên. Độ rực rỡ của màn nổ này bằng tổng năng lượng của các đốm sáng vừa bị xóa.

Bạn là trợ lý đắc lực của bác VCB, hãy giúp bác tính toán độ rực rỡ của từng màn "Bùng nổ" để đảm bảo chương trình diễn ra hoàn hảo nhất nhé!

Input

Vào từ tệp văn bản FIREWORK.INP theo cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 \le Q \le 5 \times 10^5)\) là số lượng truy vấn

• \(Q\) dòng tiếp theo, dòng thứ \(i\) mô tả sự kiện ở bước thứ \(i\) theo định dạng:

• 1 x: Sự kiện loại 1 \((0 \le x < i)\)

• 2 x y: Sự kiện loại 2 \((x \neq y)\)

Output

Ghi vào tệp FIREWORK.OUT với mỗi sự kiện loại 2 hãy in ra độ rực rỡ.

Example

4
1 0
1 1
1 1
2 0 2

4

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

1
5

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(Q \le 500\);
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài với \(Q \le 5 \times 10^3\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với chỉ có sự kiện loại 2;
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.

Cho một dãy gồm \(n\) số nguyên dương đôi một khác nhau \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) một tập được gọi là tập DSET nếu là tập con có lực lượng lớn nhất trong các tập con của tập \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) và nếu \(x\) thuộc tập thì \(2x\) sẽ không thuộc tập.

Yêu cầu: Cho \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) hãy tìm lực lượng của tập DSET và số cách khác nhau để chọn tập DSET.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(k\) \((k ≤ 10^9)\)

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) \((a_i ≤ 10^9)\).

Output

Gồm một dòng chứa hai số \(s\), \(d\), trong đó \(s\) là lực lượng của tập DSET, \(d\) là số cách khác nhau để chọn tập DSET chia dư cho \(k\).

Example

2 100
1 2

1 2

Scoring

Subtask \(1\) (\(50\) điểm): \(n ≤ 20\);

Subtask \(2\) (\(40\) điểm): \(n ≤ 10^6\);

Subtask \(3\) (\(10\) điểm): \(n \leq 10^9\) ; \(a_{i} = i\) (khi đó file dữ liệu vào chỉ gồm một dòng chứa hai số nguyên \(n, k\)).

Trong một hệ sao xa xôi, các hành tinh được bố trí trên một mạng lưới hình vuông \(n \times n\), \(n\) hàng và \(n\) cột. Các hàng được đánh số liên tiếp theo thứ tự từ \(1\) đến \(n\), các cột được đánh số liên tiếp từ \(1\) đến \(m\) theo thứ tự từ trái sang phải. Trên mạng lưới này, mỗi hành tinh lưu trữ một lượng năng lượng đặc biệt. Hành tinh nằm trên hàng thứ \(i\), cột thứ \(j\) được gọi là hành tinh \((i, j)\), ô này mang giá trị năng lượng năng lượng \(a_{ij}\) \((1 \leq |a_{ij}| \leq 10^9)\).

Đường chéo chính của một mạng lưới (hay bảng hai chiều), chính là dãy các ô \((1, 1), (2, 2), ..., (n, n)\). Phi hành gia của chúng ta đang nghiên cứu các đường bay chéo (tức là các đường chéo chính và các đường chéo song song với nó). Anh ấy phát hiện ra rằng mỗi đường bay như vậy sẽ thu được tổng năng lượng bằng tổng năng lượng của các hành tinh mà nó đi qua.

Ví dụ với mạng lưới \(A\) có kích thước \(4 \times 4\) như sau :

\begincenter
\begintabular | c | c | c | c | \hline
\(2\) & \(3\) & \(2\) & \(4\)
\hline
\(1\) & \(2\) & \(3\) & \(5\)
\hline
\(3\) & \(2\) & \(1\) & \(1\)
\hline
\(4\) & \(1\) & \(3\) & \(2\)
\hline
\endtabular
\endcenter

Ở ví dụ trên, ta có thể thấy \(2\), \(2\), \(1\), \(2\) chính là đường chéo chính, và tổng năng lượng của đường chéo này là \(2 + 2 + 1 + 2 = 7\). Ta có thể thấy, \(3\), \(3\), \(1\) là một đường chéo song song với đường chéo chính, và tổng năng lượng của đường chéo này là \(3 + 3 + 1 = 7\).

Nhiệm vụ của bạn là giúp phi hành gia tìm ra đường bay (đường chéo chính hoặc các đường chéo song song với đường chéo chính) thu được nhiều năng lượng nhất.

Input

Dòng đầu tiên chứa số nguyên \(n\) --- kích thước của mạng lưới hành tinh \((1 \leq n \leq 1000)\).

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{ij}\) (\(1 \leq |a_{ij}| \leq 10^9\)) --- năng lượng tại hành tinh hàng \(i\), cột \(j\).

Output

In ra một số nguyên --- tổng năng lượng lớn nhất có thể thu được từ một đường bay chéo (tức là một trong các đường chéo song song với đường chéo chính, hoặc đường chéo chính).

Example

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

9

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n = 1\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n \leq 50\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n \leq 1000\).