Given a sequence a of n elements, each either 1 or −1, numbered from 1 to n.
You are provided with q operations, which can be of two types:
- Type 1 operation, formatted as
1 i v
(1≤i≤n and v∈{−1,1}), which sets ai=v;
- Type 2 operation, formatted as
2 l r k
(1≤l≤r≤n and |k|≤n), which finds two integers x and y such that l≤x≤y≤r and the sum of elements from x to y in a equals k.
- The first line contains two integers n and q (1≤n,q≤105);
- The second line contains n integers a1,a2,…,an (ai∈{−1,1});
- Each of the next q lines contains an operation in the format specified above.
Output
- For each type 2 operation, print two numbers x and y that satisfy the condition. If no such pair exists, print
-1
.
Example
Input:
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
Output:
3 4
-1
2 4
1 5
Subtasks
- Subtask 1 (20 points): k=0 for all type 2 operations;
- Subtask 2 (20 points): n,q≤5000;
- Subtask 3 (30 points): No type 1 operations;
- Subtask 4 (30 points): No additional constraints.