Array Update 2

Problem

項数 N 、初項 a 、公差dの等差数列 A がある。 以下の形式で、数列を書き換える M 個の命令文が与えられるので、与えられた順序で M 回 数列 A を書き換えたときの数列 A の K項目の値を求めなさい。

• i 番目の命令文は3つの整数 x_i , y_i , z_i で与えられる。(1 ≤ i ≤ M)
  
• x_iが0だった場合、y_i項目から z_i項目までの区間において、値の順序を反転する。
  
• x_iが1だった場合、y_i項目から z_i項目までの区間において、それぞれの値を1増加させる。
  
• x_iが2だった場合、y_i項目から z_i項目までの区間において、それぞれの値を半分にする（小数点以下は切り捨てる）。
  

Input

N
a d
M
x1 y1 z1
x2 y2 z2
...
xM yM zM
K

1行目に、1つの整数 N が与えられる。 2行目に、2つの整数 a と d が空白区切りで与えられる。 3行目に、1つの整数 M が与えられる。 4行目からの M 行のうち i 行目には i 番目の命令文を表す 3 つの整数 x_i, y_i, z_i が空白区切りで与えられる。 最後の行に、1つの整数 K が与えられる。

Constraints

• 2 ≤ N ≤ 200000
• 1 ≤ a ≤ 5
• 1 ≤ d ≤ 5
• 1 ≤ M ≤ 200000
• 0 ≤ x_i ≤ 2 (1 ≤ i ≤ M)
• 1 ≤ y_i ≤ N (1 ≤ i ≤ M)
• 1 ≤ z_i ≤ N (1 ≤ i ≤ M)
• y_i < z_i (1 ≤ i ≤ M)
• 1 ≤ K ≤ N

Output

入力で与えられた順番で数列AをM回更新したときのK項目を出力せよ。

Sample Input 1

4
2 1
3
0 1 2
1 1 4
2 2 4
3

Sample Output 1

2

{ 2 , 3 , 4 , 5 }

↓ 0 1 2 ... 1項目から2項目までの区間の値の順序を反転する

{ 3 , 2 , 4 , 5 }

↓ 1 1 4 ... 1項目から4項目までの区間の値をそれぞれ1増やす

{ 4 , 3 , 5 , 6 }

↓ 2 2 4 ... 2項目から4項目までの区間の値をそれぞれ半分にする（小数点以下切り捨てる）

{ 3 , 1 , 2 , 3 }

よって3項目の値は2である。

Sample Input 2

5
1 2
3
1 2 3
2 3 5
0 1 5
1

Sample Output 2

4

{ 1 , 3 , 5 , 7 , 9 }

↓ 1 2 3 ... 2項目から3項目までの区間の値をそれぞれ1増やす

{ 1 , 4 , 6 , 7 , 9 }

↓ 2 3 5 ... 3項目から5項目までの区間の値をそれぞれ半分にする（小数点以下切り捨てる）

{ 1 , 4 , 3 , 3 , 4 }

↓ 0 1 5 ... 1項目から5項目までの区間の値の順序を反転する

{ 4 , 3 , 3 , 4 , 1 }

よって1項目の値は4である。

Note

Link

 

---