Product

Cho một dãy \(A\) gồm \(n\) phần tử. Tìm hai chỉ số \(i\) và \(j\) thỏa mãn \(i < j\) và \(A_i < A_j\) và tích \(A_i \times A_j\) là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng testcase.

• \(T\) dòng tiếp theo, mỗi dòng chứa các số \(n,l,r,x,y,z,B_1,B_2\ (2\le n \le 10^7,-2\times10^9\le l \le r \le2×10^9,0\le x,y,z,B_1,B_2<2^{32})\), với \(n\) là độ dài của dãy.

• Dãy \(A\) được sinh ra bằng thuật toán sau: Đầu tiên sinh ra dãy \(B\) gồm \(n\) phần tử. \(B_1\) và \(B_2\) đã cho, với mọi \(i>2\):

• \(B_i=(B_{i-2} \times x + B_{i-1} \times y+z)\) mod \(2^{32}\).

• \(A_i=B_i\) mod \((r-l+1)+l\). Khi đó \(-2\times10^9\le A_i\le2\times10^9\).

• Tổng \(n\) trong tất cả các testcase không vượt quá \(2 \times 10^7\).

Output

• Với mỗi testcase, ghi ra tích \(A_i \times A_j\) nhỏ nhất tìm được, nếu không có \(i,j\)thỏa mãn, ghi ra \(-1\).

Example

2
4 -5 5 11 13 17 0 3
5 0 100 0 1 0 42 42

-15
-1

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Tổng \(n\) không vượt quá \(2 \times 10^3\).
• Subtask \(2\) (\(10\%\) số điểm): Tổng \(n\) không vượt quá \(2 \times 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): Tổng \(n\) không vượt quá \(2 \times 10^6\).
• Subtask \(4\) (\(50\%\) số điểm): Tổng \(n\) không vượt quá \(2 \times 10^7\).