Processing math: 100%
Sequences of sum <span class="MathJax_Preview" style="color: inherit;"><span class="MJXp-math" id="MJXp-Span-1"><span class="MJXp-mi MJXp-italic" id="MJXp-Span-2">k</span></span></span><script type="math/tex" id="MathJax-Element-1">k</script> - MarisaOJ: Marisa Online Judge

Sequences of sum k

Time limit: 1000 ms
Memory limit: 256 MB

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.

Input

  • 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.