PEG Judge - Campfire Cooking

Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Problem G: Campfire Cooking

Esdeath is currently enjoying a wonderful dinner with subordinates in her army. There is a giant pot on a campfire, and N (2 ≤ N ≤ 200000) soldiers surrounding the pot in a circle, numbered clockwise from 1 to N. 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 i's food tastes best when it is cooked between A_i and B_i degrees Celsius, inclusive. We shall refer to this as the optimal temperature range.

The entire campfire cooking session will last M (1 ≤ M ≤ 200000) minutes. During each of these minutes, one of three possible events will occur:

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

After each time Esdeath performs this event, the temperature of the pot will change based on three constant values X, Y, and Z (0 ≤ X, Y ≤ 1000; 1 ≤ Z ≤ 100000). The new temperature after each instance of this event is determined by the formula: T_new = ((T_old*X + F*Y) mod Z) + 1, where F 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 F, the number of types of foods that have been tossed into the pot.
The i-th 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 L and H (1 ≤ i ≤ N; 1 ≤ L ≤ H ≤ Z).
For this event, Esdeath would like to know, hypothetically, if all soldiers between i and j were to put some of their food into the pot in increasing order of the A_i temperatures of their food (the lower bounds of their foods' optimal temperature ranges), what would be the A_i temperature of the k-th soldier who places food into the pot? If no such value exists, output -1.

Input Format

Line 1: Six integers N, M, T, X, Y, and Z.
Next N lines: line i+1 will contain two integers A_i and B_i, the optimal temperature range for soldier i's initial type of food.
Next M lines: line i+N+1 will describe the event that happens in the i-th minute of the cooking session. Each line will be in one of the following three formats to represent the three types of events:

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

At any given time the pot's temperature T will satisfy 1 ≤ T ≤ Z. Furthermore, the total number of type 2 events will not exceed 25000.

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 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 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 1

Sample Output 2

Sample Output 3

Explanation for Sample 1

The pot starts at a temperature of 4 degrees Celsius. The range of temperatures is [3, 4].
All soldiers participate, and 4 types of food are thrown into the pot. The temperature becomes (4*1 + 4*1) mod 10 + 1 = 9 degrees Celsius.
Soldiers 2, 3, and 4 participate, and 1 type of food is thrown into the pot. The temperature becomes (9*1 + 1*1) mod 10 + 1 = 1 degrees Celsius.
The third soldier cannot throw any food into the pot. The temperature becomes (1*1 + 0*1) mod 10 + 1 = 2 degrees Celsius.
All soldiers participate again, and 2 types of food are thrown into the pot. The temperature becomes (2*1 + 2*1) mod 10 + 1 = 5 degrees Celsius, and the cooking session ends.