Array Update

Time Limit : 1 sec, Memory Limit : 262142 KB

Array Update

Problem

項数 N、初項 a、公差 d の等差数列 A がある。以下の形式で数列を更新する命令文が M 個与えられるので、与えられた順序で数列 AM 回更新したときの K 項目の値を求めよ。

  • i 番目の命令文は3つの整数 xi , yi , zi で表される(1 ≤ iM)。
  • xiが0だった場合、yi項目の値と zi項目の値を入れ替える。
  • xiが1だった場合、yi項目の値を zi項目の値に書き換える。

Input

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

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

Constraints

  • 1 ≤ N ≤ 108
  • 1 ≤ a ≤ 5
  • 1 ≤ d ≤ 5
  • 1 ≤ M ≤ 10
  • 0 ≤ xi ≤ 1 (1 ≤ iM)
  • 1 ≤ yiN (1 ≤ iM)
  • 1 ≤ ziN (1 ≤ iM)
  • yizi (1 ≤ iM)
  • 1 ≤ KN

Output

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

Sample Input 1

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

Sample Output 1

11

{ 2 , 5 , 8 , 11 , 14 }
  ↓
0 2 5 … 2項目の値と5項目の値を入れ替える
  ↓
{ 2 , 14 , 8 , 11 , 5 }
  ↓
0 3 5 … 3項目の値と5項目の値を入れ替える
  ↓
{ 2 , 14 , 5 , 11 , 8 }
  ↓
1 2 4 … 2項目の値を4項目の値に書き換える
  ↓
{ 2 , 11 , 5 , 11 , 8 }
よって2項目は11である。

Sample Input 2

6
5 5
4
0 1 2
1 1 2
0 4 1
1 1 6
3  

Sample Output 2

15

Source: Aizu Competitive Programming Camp 2015 Day2 , Japan, 2015-09-22