## Campfire Cooking

View as PDF

Points: 40 (partial)
Time limit: 1.5s
Memory limit: 1G

Authors:
Problem type
##### Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Esdeath is currently enjoying a wonderful dinner with subordinates in her army. There is a giant pot on a campfire, and soldiers surrounding the pot in a circle, numbered clockwise from to . Each soldier holds a very large supply of a specific type of food that tastes best when cooked at a specific range of temperatures. Soldier 's food tastes best when it is cooked between and degrees Celsius, inclusive. We shall refer to this as the optimal temperature range.

The entire campfire cooking session will last minutes. During each of these minutes, one of three possible events will occur:

1. Esdeath would like to try a combination of foods, so all soldiers with a number between and (; note: it is not necessarily true that ) will pitch in some food if the type of food they hold tastes best within a certain range of the pot's current temperature degrees Celsius. That is, if a soldier is between soldiers and inclusive, they must contribute if their optimal temperature range overlaps with the range . Here, between means starting from the soldier and going clockwise around the circle, considering every soldier you pass up to and including the soldier.

After each time Esdeath performs this event, the temperature of the pot will change based on three constant values , , and . The new temperature after each instance of this event is determined by the formula: , where is the number of foods tossed into the pot. We'll assume that each soldier has a very large quantity of their own type of food, and will always be able to contribute if his or her temperature range is right. Every time this event is called, please determine , the number of types of foods that have been tossed into the pot.

2. The soldier gets a new type of food, getting rid of their old type of food. The new type of food will have an optimal temperature range between and .

3. For this event, Esdeath would like to know, hypothetically, if all soldiers between and were to put some of their food into the pot in increasing order of the temperatures of their food (the lower bounds of their foods' optimal temperature ranges), what would be the temperature of the soldier who places food into the pot? If no such value exists, output -1.

#### Input Specification

Line : Six integers , , , , , and .
Next lines: line will contain two integers and , the optimal temperature range for soldier 's initial type of food.
Next lines: line will describe the event that happens in the minute of the cooking session. Each line will be in one of the following three formats to represent the three types of events:

• Type events will be in the format: 1 i j L H
• Type events will be in the format: 2 i L H
• Type events will be in the format: 3 i j k

At any given time the pot's temperature will satisfy . Furthermore, the total number of type events will not exceed .

#### Sample Input 1

5 4 4 1 1 10
1 3
4 6
7 9
3 5
2 4
1 1 5 1 0
1 2 4 0 0
1 3 3 0 0
1 3 2 0 0

#### Sample Output 1

4
1
0
2

#### Sample Explanation 1

The pot starts at a temperature of degrees Celsius. The range of temperatures is .
All soldiers participate, and types of food are thrown into the pot. The temperature becomes degrees Celsius.
Soldiers , , and participate, and type of food is thrown into the pot. The temperature becomes degrees Celsius.
The third soldier cannot throw any food into the pot. The temperature becomes degrees Celsius.
All soldiers participate again, and types of food are thrown into the pot. The temperature becomes degrees Celsius, and the cooking session ends.

#### Sample Input 2

3 10 1 2 3 10
1 1
1 5
1 10
1 1 3 0 9
2 3 10 10
1 1 3 1 1
1 1 3 0 9
1 1 3 0 1
2 2 9 9
1 1 3 0 2
1 1 3 2 0
1 1 2 0 0
1 1 2 0 0

#### Sample Output 2

3
2
3
1
2
1
0
1

#### Sample Input 3

5 12 1 0 0 5
3 3
1 1
3 3
4 4
2 2
3 1 5 1
3 2 1 2
3 3 2 3
3 4 3 4
3 5 4 5
3 1 3 1
3 1 3 2
3 1 3 3
3 4 2 4
3 1 2 3
3 4 1 5
3 4 1 2

#### Sample Output 3

1
2
3
3
4
1
3
3
4
-1
-1
3

#### Constraints

##### Subtask 1 [8%]

Additionally, there will be no events of type .

##### Subtask 2 [17%]

In all events of type , .
Additionally, there will be no events of type .

##### Subtask 3 [20%]

and .
Additionally, there will be no events of type .

##### Subtask 4 [15%]

There will only be events of type .

##### Subtask 5 [17%]

There will be no events of type .

##### Subtask 7 [3%]

There are no additional constraints.