Recently, Little Sub is obsessed with a game named Assassin Heaven.
In the game, Little Sub is armed with a X degrees weapon initially and he is going to beat n Assassins in order. The player can kill Assassin i only when his weapon degree is not lower than the enemy’s degree. If you successfully defeat Assassin i, you can choose to get his weapon which is degree D[i].
Each time when Little Sub plays this game, the game will generate each Assassin i with random degrees ranged in [1..M[i]].
Please calculate how many different ways of generating the enemy that Little Sub will win the game. To increase the difficulty, we may change some D[i] or M[i] and you have to calculate the answer each time.
We consider two generating ways as different when there exists at least one assassin with different degrees.
The first line contains three positive integer n,q,X(1 ≤ n,q ≤ 10^5,1 ≤ X ≤ 10^9, indicating the number of the enemy, the number of queries and the initial weapon degree.
The second line contains n integers M[i](1 ≤ M[i] ≤ 10^9).
The third line contains n integers D[i](1 ≤ D[i] ≤ 10^9).
The following q lines represent all queries.
In each query, there are three integer opt,x,y(1 ≤ x ≤ n,1 ≤ y ≤ 10^9) in one line.
If opt = 0, it means changing M[x] to y permanently.
If opt = 1, it means changing D[x] to y permanently.
For each query, output the answer in one line. Since the answer maybe very large, output the answer modulo 10^9 + 7.