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 $N$ $(2\le N\le 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\le M\le 200000)$ 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 $i$ and $j$ ($1\le i,j\le N$; note: it is not necessarily true that $i\le 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\le L,H\le 100000)$. Here, between means starting from the $i^{\text{th}}$ soldier and going clockwise around the circle, considering every soldier you pass up to and including the $j^{\text{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\le X,Y\le 1000;1\le Z\le 100000)$. The new temperature after each instance of this event is determined by the formula: $T_{\text{new}}=((T_{\text{old}}\times X+F\times Y)modZ)+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.

2. The $i^{\text{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\le i\le N;1\le L\le H\le Z)$.

3. 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^{\text{th}}$ soldier who places food into the pot? If no such value exists, output -1.

Input Specification

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^{\text{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\le T\le 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 Output 1

4
1
0
2

Sample Explanation 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\times 1+4\times 1)mod10+1=9$ degrees Celsius.
Soldiers $2$, $3$, and $4$ participate, and $1$ type of food is thrown into the pot. The temperature becomes $(9\times 1+1\times 1)mod10+1=1$ degrees Celsius.
The third soldier cannot throw any food into the pot. The temperature becomes $(1\times 1+0\times 1)mod10+1=2$ degrees Celsius.
All soldiers participate again, and $2$ types of food are thrown into the pot. The temperature becomes $(2\times 1+2\times 1)mod10+1=5$ 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%]

$N,M\le 1000$
Additionally, there will be no events of type $3$.

Subtask 2 [17%]

$N,M\le 100000$
In all events of type $1$, $L=H=0$.
Additionally, there will be no events of type $3$.

Subtask 3 [20%]

$N,M\le 100000$
$X=1$ and $Y=0$.
Additionally, there will be no events of type $3$.

Subtask 4 [15%]

$N,M\le 100000$
There will only be events of type $1$.

Subtask 5 [17%]

$N,M\le 100000$
There will be no events of type $3$.

Subtask 6 [20%]

$N,M\le 100000$

Subtask 7 [3%]

There are no additional constraints.