Hi everyone!

I have just participated in an IT contest in my city recently. And there was a segment tree problem that for now, I cant think of the way to use the segment tree properly. Here's the problem:

Given an array a contains only two numbers: 1 and -1, all the elements index from 1 to n.

Input:

The first line contains two integer n and q (1 <= n,q <= 10^5), corresponding to the size of the array and number of operation. The next line contains array of integers a1, a2, a3, ..., an of length n (a[i] ∈ {1;-1}). The next q following lines contain the description of the operations. The description of each operation is as follows:

• 1 i v: set the element with index i to v (1 <= i <= n, v ∈ {1;-1})

• 2 l r k (1 <= l <= r <= n, |k| <= n): this operation needs to find two number x, y (l >= x >= y >= r) such that the sum of all element from x to y equals to k.

Output

For each operation of the second type print the corresponding x, y. If no answer exists, print -1.

• Example:

I first approached this problem by doing some classic segment tree to find sum in a subsegment of the array, but I was soon realized that if I do that way, I can't find the proper way to find the number x and y. So I'm wonder what is the another way to approach this segment tree question more optimal.

And finally, thank you for reading my blog!