Hotpot Feast Simulation

In a grand hotpot feast, there are \( n \) types of food (each available in an infinite quantity) and a spicy soup base. Each food type \( i \) takes \( s_i \) units of time to be cooked. When a food of type \( i \) is added to the pot at time \( T \), it becomes cooked at time \( T+s_i \) and remains cooked until it is removed.

There are four kinds of events happening at integer time moments during the feast (which lasts up to \( 10^9 \) time units):

• 0 id: SkyDec adds one food of type id into the pot.
• 1: Yazid searches the pot for any cooked food and picks the one he likes best. According to Yazid, all cooked foods are tasty but he prefers food with a smaller id. If there is no cooked food, Yazid becomes angry.
• 2 id: YJQQQAQ searches for a food of type id in the pot. If there is no food of that type at all, he becomes angry. If there is any cooked food of that type, he takes one (removing it from the pot) and eats it (output 0). Otherwise, if there are only uncooked foods of that type, he asks: how many more time units does the one that has been waiting the longest need to be cooked? (output the remaining time)
• 3 l r: SkyDec queries the total number of cooked foods in the pot with types in the interval \( [l,r] \).

All events occur in chronological order. Assume the current time equals the event index (starting from 0). For a food added at time \( T \), its finish time is \( T+s_i \). Before processing any event at time \( t \), all foods whose finish times are \( \le t \) become cooked automatically.

For operations that remove a cooked dish (events of type 1 and type 2 when a cooked dish exists), the dish is removed from the pot. For event type 2, if only uncooked dishes exist, the dish remains in the pot.

inputFormat

The first line contains two integers ( n ) and ( Q ), denoting the number of food types and the number of events respectively. The second line contains ( n ) integers: ( s_1, s_2, \dots, s_n ) where ( s_i ) is the cooking time for food type ( i ). Each of the next ( Q ) lines describes an event in one of the formats below:

• 0 id • 1 • 2 id • 3 l r

All integers are separated by spaces.

outputFormat

For each event of type 1, 2, and 3, output one line containing the result:

• For an event of type 1: If there is at least one cooked food in the pot, remove one cooked dish of the smallest type id and output its id; otherwise, output -1.

• For an event of type 2 with food type id:

• If the pot does not contain any food of that type, output -1.
• If there is at least one cooked dish of that type, remove one cooked dish and output 0.
• Otherwise (only uncooked dishes exist), do not remove any dish and output the remaining time for the dish that has been waiting the longest (i.e. its finish time minus the current time).

• For an event of type 3: Output the total number of cooked dishes in the pot among food types in the range ( [l,r] ).

sample

3 7
2 3 1
0 1
0 2
1
2 2
0 3
3 1 3
2 2

1
1
2
0

</p>