You are given an array $a$ of length $n$. You need to process $q$ queries. Each query is one of the following two types:

$1.$ $x$ - What is the value of $a_x$ modulo $10^9+7$?

$1.$ $x$ - What is the value of $a[x]$ modulo $10^9+7$?

$2.$ $x, y, b, c$ - For every $i$ in the range $[x,y]$ $a_i$ becomes max($a_i$, $b*i^c$)

$2.$ $x, y, b, c$ - For every $i$ in the range $[x,y]$ $a[i]$ becomes max(a[i], $b*i^c$)

h2. Date de intrare
The first line of the input file $abp.in$ contains the integer $n$, the length of the array.

The second line of the input contains $n$ integers, the $i$-th being $a_i$

The second line of the input contains $n$ integers, the $i$-th being $a[i]$

The third line of the input contains an integer $q$, the number of queries.

* $1 ≤ x, y ≤ n ≤ 10^5$
* $1 ≤ q ≤ 2 * 10^5$

* $1 ≤ a_i, b, c ≤ 10^5$

* $1 ≤ a[i], b, c ≤ 10^5$
* The scores obtained now may be different compared to the ones from the original contest

h2. Exemplu