Little Sub and Game

Tags:
Time Limit:  15 s      Memory Limit:   256 MB
Submission：131     AC：13     Score：99.20

Description

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.

Input

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.

Output

For each query, output the answer in one line. Since the answer maybe very large, output the answer modulo 10^9 + 7.

Samples

input
5 3 2 4 2 3 5 7 3 2 4 3 2 1 3 5 0 2 3 0 2 10
output
192 300 450 450