F. Goalkeeper of 7 games (or less)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every Brazilian knows Ryan Ochoa very well, the Mexican goalkeeper who park the bus the goal against Brazil in the 2014 World Cup. More than that, the guy becomes the best goalkeeper in history during any World Cup period and hibernates for the following 4 years. What nobody knows is that in reality, he is training his successor as the best goalkeeper in World Cups: you! Now you need to buy one pair for yourself and one pair for Ochoa. In the store, there are exactly $$$N$$$ gloves on display, arranged in a line. The glove in position $$$i$$$ has size $$$A_i$$$. The size you both wear doesn't matter, as you are the best in the world in your position. However, to not hinder the performance in training, it's crucial to choose the same size $$$X$$$ for both your gloves and the same size $$$Y$$$ for Ochoa's ($$$X$$$ and $$$Y$$$ can be different). Every day, the gloves available for sale can change! They are always defined by an interval $$$[l, r]$$$ that represents the positions of the gloves for sale at that moment. Moreover, the glove at position $$$i$$$ can be replaced by another of a different size. We have $$$Q$$$ changes in total, and they are described as follows:

  • $$$1$$$ $$$\ell \, r$$$: The range of gloves for sale has changed to $$$[l, r]$$$, and at this moment, you must say whether it's possible to buy a pair of gloves for yourself and one for Ochoa;
  • $$$0$$$ $$$i \, x$$$: the glove in position $$$i \in \{1 \ldots N\}$$$ was exchanged for a glove of size $$$1 \leq x \leq 10^9$$$.
Input

The first line contain two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$).

The second line contains a sequence $$$A_i$$$ of size $$$n$$$ ($$$1 \leq A_i \leq 10^9$$$).

The next $$$q$$$ lines contains the operations described in the statement.

Output

For each operation of type $$$1$$$:

  • If it is possible, print 4 integers that represent the position of the gloves to buy. If there are more than one answear, print any. The order that you print the gloves does not matter.
  • If it is not possible, print $$$-1$$$.
Examples
Input
4 3
1 1000000000 1 1
1 1 4
0 4 1000000000
1 1 4
Output
-1
2 4 1 3
Input
10 8
1 1 2 3 4 5 5 6 7 10
1 1 6
1 1 7
0 4 2
1 1 6
0 1 5
1 1 6
0 4 3
1 1 7
Output
-1
6 7 1 2
3 4 1 2
1 6 3 4
-1