Bài tập

Cho dãy \(a\) gồm \(n\) số \(1\) và \(-1\), các phần tử được đánh số từ \(1\) đến \(n\).

Cho \(q\) thao tác gồm một trong hai dạng:

• Thao tác loại \(1\) có dạng "\(1\) \(i\) \(v\)" (\(1 \le i \le n\) và \(v \in \{1,-1\}\)), thao tác này sẽ gán \(a_i = v\).

• Thao tác loại \(2\) có dạng "\(2\) \(l\) \(r\) \(k\)" (\(1 \le l \le r\ le n\) và \(|k| \le n\)), thao tác này cần tìm hai số nguyên \(x,y\) thỏa mãn \(l \le x \le y \le r\) và tổng các phần tử từ \(x\) đến \(y\) của dãy \(a\) đúng bằng \(k\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n,q\) (\(1 \le n,q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(a_i \in \{1,-1\}\)).

• Mỗi dòng trong \(q\) dòng tiếp theo chứa một thao tác theo định dạng như trên đề bài.

Output

• Với mỗi thao tác loại \(2\), in ra hai số \(x,y\) bất kì thỏa mãn điều kiện. Nếu không tồn tại đáp án, in ra "-1".

Example

5 8
1 -1 -1 1 1
2 1 4 0
2 1 4 -3
1 4 -1
2 1 5 -3
1 3 1
1 1 -1
1 5 -1
2 1 5 -3

1 2
-1
2 4
1 5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 0\) với mọi thao tác loại \(2\).

• Subtask \(2\) (\(20\%\) số điểm): \(n,q \le 5000\).

• Subtask \(3\) (\(30\%\) số điểm): không có thao tác loại \(1\).

• Subtask \(4\) (\(30\%\) số điểm): 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.

Cho một dãy gồm \(N\) số nguyên \(a_{1}, a_{2}, … , a_{n}\). Số hạng \(a_{i}\) \((1 ≤ i ≤ N)\) được gọi là số hạng dẫn đầu của dãy nếu nó lớn hơn hay bằng tất cả các số hạng từ chỉ số \(i + 1\) đến \(N\). Số hạng \(a_{n}\) luôn là một số hạng dẫn đầu.

Yêu cầu: Hãy liệt kê tất cả các số hạng dẫn đầu theo thứ tự của chúng trong dãy.

Input

Đọc từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên dương \(N\) \((1 ≤ N ≤ 10^6)\) là số lượng số hạng của dãy;

• Dòng tiếp theo ghi \(N\) số nguyên \(a_{1}, a_{2}, … , a_{n}\) \((|a_{i}| ≤ 10 ^ 9, i = 1, 2, … , N)\), các số cách nhau một dấu cách.

Output

Ghi ra tệp văn bản BAI3.OUT các số dẫn đầu theo thứ tự, các số ghi trên một dòng và
cách nhau một dấu cách

Example

7
50 1 40 2 40 4 30

50 40 40 30 

Scoring

Có \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N \leq 5000\).

\(40\%\) số test còn lại không có ràng buộc gì thêm.

Trường Đại học Công nghệ Tương lai vừa cho ra mắt một hệ thống AI đặc biệt mang tên "Mai Mối Chuẩn Gen", với nhiệm vụ giúp sinh viên cô đơn tìm được nửa kia phù hợp nhất dựa trên chỉ số "tương thích cảm xúc".

Có \(n\) sinh viên tham gia hệ thống, mỗi người được hệ thống đánh giá bằng một chỉ số \(a_1, a_2, ..., a_n\) thể hiện mức độ đồng điệu về cảm xúc.

Hệ thống hoạt động bằng cách chia dãy chỉ số cảm xúc thành các đoạn con liên tiếp, không giao nhau. Một đoạn được xem là tối ưu nếu trung bình cộng của các chỉ số trong đoạn đúng bằng một giá trị lý tưởng \(x\) mà hệ thống đưa ra.

Mỗi khi có sinh viên đăng ký tham gia, hệ thống sẽ yêu cầu trả lời một truy vấn dạng:

Trong khoảng từ người thứ \(l\) đến người thứ \(r\), có thể chia được tối đa bao nhiêu đoạn con liên tiếp, không giao nhau sao cho trung bình cộng của mỗi đoạn đúng bằng \(x\)?

Bạn được giao nhiệm vụ xử lý \(q\) truy vấn như vậy, để giúp hệ thống hoạt động hiệu quả hơn!

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(q\), \(x\) \((1 \le n, q \le 2 \cdot 10^5, 1 \le x \le 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) là chỉ số cảm xúc của từng sinh viên \((1 \le a_i \le 10^6)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\), \(r_i\) \((1 \le l_i \le r_i \le n)\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là đáp án cho truy vấn thứ \(i\) --- số đoạn con liên tiếp, không giao nhau trong đoạn \([l_i, r_i]\) sao cho trung bình cộng đúng bằng \(x\).

Example

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

4

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 200\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 2000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm không có ràng buộc gì thêm.