The Noisy Restaurant

In a restaurant, customers not only enjoy their meals but sometimes have to deal with annoying noise. In this problem, each time a person at seat k emits noise with intensity j (with a decay coefficient which we assume to be 1), the noise received at another seat i is computed in one of two ways:

• If there is no noise reduction device installed along the path from seat k to seat i (see details below), then the noise reaching seat i is given by \[ \max\Bigl(0, j - |i - k|\Bigr). \]</p>
• If there exists a noise reduction device built before the noise was emitted and it is encountered on the straight-line path from k to i, let \(x\) be the first such device encountered. In this case the noise reaching seat i becomes \[ \max\Bigl(0, j - |k-x| - 2|i-x|\Bigr). \] Note that the penalty after the device is harsher (multiplied by 2).

Furthermore, each noise reduction device has a drawback. If a noise is emitted from a seat that currently has a noise reduction device installed, then that device is immediately destroyed and will not affect the current or any future noise events.

The system processes m events in chronological order, and the following types of events may occur:

1. 1 i j: The person sitting at seat \(i\) emits noise of intensity \(j\). (If seat \(i\) has a noise reduction device installed, it is destroyed immediately before the emission.)
2. 2 i: Query the noise received at seat \(i\). The noise level at any seat is defined as the maximum noise level reaching that seat from any noise emission so far.
3. 3 i: The management installs a noise reduction device at seat \(i\). If there is already a device at \(i\), this event has no effect.

Important: A noise reduction device only affects noise events that are emitted after it is installed. That is, when processing a noise emission, only devices already in place affect its propagation.

Your task is to simulate these events and answer the queries accordingly.

inputFormat

The input begins with an integer (m) representing the number of events. The following (m) lines each contain an event in one of the following formats:

1. 1 i j: A noise emission event at seat \(i\) with intensity \(j\). (If seat \(i\) currently has a noise reduction device, it is destroyed immediately.)
2. 2 i: A query event asking for the noise level at seat \(i\). The noise level at a seat is the maximum noise value received from all previous noise emissions.
3. 3 i: A noise reduction device installation event at seat \(i\). If a device is already installed at \(i\), the event is ignored.

Note: When a noise propagates from its source at seat \(k\) to another seat \(i\), the computation is as follows:

• If there is no noise reduction device (from those installed prior to the emission) between \(k\) and \(i\), the noise at \(i\) is \[ \max\Bigl(0, j - |i-k|\Bigr). \]
• If there is a device, let \(x\) be the first device encountered along the straight-line path from \(k\) to \(i\). Then the noise at \(i\) is \[ \max\Bigl(0, j - |k-x| - 2|i-x|\Bigr). \]

Initially, no noise reduction devices are installed.

outputFormat

For each query event (of the form 2 i), output a single integer on a separate line representing the maximum noise level received at seat (i) from all noise emissions processed so far.

sample

6
1 3 10
3 5
1 2 8
2 4
1 5 12
2 6

9
11

</p>