406600: GYM102452 H Hold the Line

Trench warfare is a type of land warfare using occupied fighting lines largely comprising military trenches, in which troops are well-protected from the enemy's small arms fire and are substantially sheltered from artillery. The most famous use of trench warfare is the Western Front in World War I. "Trench warfare" has become a byword for stalemate, attrition, sieges, and futility in conflict. Trench warfare proliferated when a revolution in firepower was not matched by similar advances in mobility, resulting in a gruelling form of warfare in which the defender held the advantage.

Trench diagram from a 1914 British infantry manual. Public domain.

As a senior commander in the army, you must hold the ground with your soldiers. You have constructed a defence line consisting of $$$N$$$ trenches numbered from $$$1$$$ to $$$N$$$, each of which is empty initially. The soldiers are waiting for your order, and each soldier has a preferred shooting height.

As the battle goes on, the following two events may happen:

• A soldier with the preferred shooting height $$$h$$$ is sent to garrison an empty trench.
• An enemy with height $$$H$$$ is sighted, and only the soldiers garrisoned in trenches numbered between $$$L$$$ and $$$R$$$ can shoot that enemy. In order to improve the chance to hit and thus save the bullets, it is necessary to select a soldier whose preferred shooting height is as close as possible to the enemy's height to shoot the enemy. You need to know the difference between the selected soldier's preferred shooting height and the enemy's height.

Your deputy in charge of intelligence has predicted that $$$M$$$ events would happen during the battle. To make better preparations for the battle, you need to write a program to simulate the events and study the outcome.

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \le T \le 10^5)$$$, the number of cases.

For each case, the first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 5 \cdot 10^5, 1 \le M \le 10^6$$$), the number of trenches and the number of events respectively.

The next $$$M$$$ lines each contains three or four integers, describing the events in time order. The $$$i$$$-th line $$$(1 \le i \le M)$$$ describes the $$$i$$$-th event. The first integer in each line denotes $$$type$$$ ($$$type \in \{0,1\}$$$). If $$$type=0$$$, two more integers $$$x,h$$$ will follow, denoting that a soldier with the preferred shooting height $$$h \ (1 \le h_i \le 10^9)$$$ is now garrisoned at an empty trench $$$x \ (1 \le x \le N)$$$. If $$$type=1$$$, three more integers $$$L,R,H$$$ will follow, denoting that an enemy with height $$$H \ (1 \le H \le 10^9)$$$ is sighted, and only soldiers in trenches numbered from $$$L$$$ to $$$R$$$ ($$$1 \le L \le R \le N$$$) can shoot that enemy.

It is guaranteed that the sum of $$$N$$$ over all cases doesn't exceed $$$5 \cdot 10^5$$$, and the sum of $$$M$$$ over all cases doesn't exceed $$$10^6$$$.

For each event with $$$type=1$$$, print a single integer in a single line, the difference between the selected soldier's preferred shooting height and the enemy's height. If no soldier is garrisoned in trenches numbered from $$$L$$$ to $$$R$$$, print the integer $$$-1$$$ instead.

1
3 5
1 1 3 2
0 1 1
0 3 3
1 1 2 2
1 2 3 2

-1
1
1