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 \leq i \leq n$ and $v \in \\{-1,1\\}$), which sets $a_i = v$;
- Type 2 operation, formatted as `2 l r k` ($1 \leq l \leq r \leq n$ and $|k| \leq n$), which finds two integers $x$ and $y$ such that $l \leq x \leq y \leq 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 \leq n, q \leq 10^5$);
- The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($a_i \in \\{-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 \leq 5000$;
- **Subtask 3 (30 points)**: No type $1$ operations;
- **Subtask 4 (30 points)**: No additional constraints.
