当前没有测试数据。

题目描述

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $is 3 (i.e. [2,2,3‾,3,10][2,2,\underline{3},3,10]$). Median of the array [1,5,8,1] is 1 (i.e. $[1,\underline{1},5,8]$).

At first, you're given an empty sequence. There are N operations. The i-th operation contains two integers LiL_iLi​ and RiR_iRi​. This means that adding Ri−Li+1R_i-L_i+1Ri​−Li​+1 integers Li,Li+1,...,RiL_i, L_i+1, ... , R_iLi​,Li​+1,...,Ri​ into the sequence. After each operation, you need to find the median of the sequence.

输入格式

The first line of the input contains an integer $N\ (1 \leq N \leq 400000)N$ as described above.

The next two lines each contains six integers in the following format, respectively:

$M1X_1\ X_2\ A_1\ B_1\ C_1\$ $M2Y_1\ Y_2\ A_2\ B_2\ C_2\ M_2$

These values are used to generate Li,RiL_i, R_iLi​,Ri​ as follows:

We define: $ M1X_i = (A_1 \times X_{i-1} + B_1 \times X_{i-2} + C_1)\ module\ M_1$ module M1​, for i=3 to Ni = 3\ to\ Ni=3 to N

• Yi=(A2×Yi−1+B2×Yi−2+C2) module M2Y_i = (A_2 \times Y_{i-1} + B_2 \times Y_{i-2} + C_2)\ module\ M_2Yi​=(A2​×Yi−1​+B2​×Yi−2​+C2​) module M2​, for i=3 to Ni = 3\ to\ Ni=3 to N

We also define:

• Li=min(Xi,Yi)+1L_i = min(X_i, Y_i) + 1Li​=min(Xi​,Yi​)+1, for i=1 to Ni = 1\ to\ Ni=1 to N.
• Ri=max(Xi,Yi)+1R_i = max(X_i, Y_i) + 1Ri​=max(Xi​,Yi​)+1, for i=1 to Ni = 1\ to\ Ni=1 to N.

Limits: $1 \leq N \leq 400000$ $0 \leq A_1 < M_1$​ $0 \leq A_2 < M_2$​ $0 \leq B_1 < M_1$​ $0 \leq B_2 < M_2$​ $10 \leq C_1 < M_1$​ $0 \leq C_2 < M_2$​ $0 \leq X_1 < M_1$​ $0 \leq X_2 < M_1$​ $0 \leq Y_1 < M_2$​ $0 \leq Y_2 < M_2$​ $1 \leq M_1 \leq 10^9$ $1 \leq M_2 \leq 10^9$

输出格式

You should output lines. Each line contains an integer means the median.

样例

样例输入 1

5
3 1 4 1 5 9
2 7 1 8 2 9

样例输出 1

3
4
5
4
5