Amazing John's Flower Walk

Amazing John loves flowers. In his garden, there are (n) flowers arranged in a line. Each flower is rated either beautiful or not: a beautiful flower has a beauty value of (2) and an unappealing one has a beauty value of (1).

Every day, Amazing John takes a walk in his garden. A walk is defined as choosing a contiguous segment of flowers, starting from the (l)-th flower and ending at the (r)-th flower (inclusive), and summing up their beauty values.

Now, given a target sum (s), your task is to determine if there exists a walking scheme such that the sum of beauty values from the (l)-th to the (r)-th flower is exactly (s). If multiple valid segments exist, you must output the one with the smallest possible starting index (l).

Moreover, to keep his walks interesting, Amazing John may update the beauty value of a flower at any time. Note that the changes persist through subsequent queries.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \leq n, q \leq 10^5)\), representing the number of flowers and the number of operations.

The second line contains \(n\) integers, each either \(1\) or \(2\), representing the beauty values of the flowers.

Each of the next \(q\) lines represents an operation in one of the following formats:

• 1 s: A query operation. Find a contiguous segment of flowers whose beauty sum is exactly \(s\) and having the smallest possible starting index \(l\). If such a segment exists, output its starting and ending 1-based indices l r; otherwise, output -1.
• 2 i v: An update operation. Change the beauty value of the \(i\)-th flower to \(v\) (where \(v\) is either \(1\) or \(2\)).

outputFormat

For each query operation (those starting with 1 s), output a single line:

• If a valid segment exists, print its starting and ending indices l and r (1-indexed), separated by a space.
• If no valid segment exists, print -1.

sample

5 5
1 2 1 2 1
1 3
2 3 2
1 5
1 7
1 10

1 2
1 3
1 4
-1