Description

A parking lot has n parking spaces, each with a size s_i. There are m events, and each event j is one of two types:

1. At time t_j, a car of size x arrives, preferring parking space l_j, and will leave at time t_j + a_j.
2. At time t_j, check how many parking spaces of size y are available. If a car leaves the parking lot at the moment of a query, the query result reflects the state after the car has left.

For each event of type 1, assign a parking space based on these rules:

1. Choose the smallest parking space that is >= x.
2. If multiple spaces meet rule 1, pick the one closest to the preferred space l_j.
3. If multiple spaces meet rule 2, choose the one with the smallest index.
4. If no space meets rule 1, output -1 and skip the operation.

Input

The first line contains two positive integers n and m, representing the number of parking spaces and the number of events.

The second line contains n positive integers s₁ to s_n, representing the size of each parking space.

The next m lines each describe an event, with event i presented in one of two formats:

1. 1 ti x li ai: At time t_i, a car of size x arrives, preferring to park as close as possible to space l_i, and will stay for a_i time units.
2. 2 ti y: At time t_i, query how many parking spaces of size y are available.

Output

For each car arrival event, output the assigned parking space number, or -1 if no space can be assigned. For each parking space query event, output the corresponding result.

Constraints

• 1 <= n, m <= 2 * 10⁵
• 1 <= s_i, t_i, x, a_i, y <= 10⁹
• t_{i - 1} < t_i
• 1 <= l_i <= n

Subtasks

• Testcase 1: Each parking space has a unique size, and whenever a vehicle arrives, there is always a parking space of size = x available, a_i = 10⁹
• Testcase 2: a_i = 10⁹, l_i = 1
• Testcases 3, 4: l_i = 1
• Testcase 5: a_i = 10⁹
• Testcases 6, 7: No additional constraints.

Sample Input  Download

Sample Output  Download

Tags

Discuss