Хлопчику Халеку дуже сподобалась алгебра в університеті. Там він дізнався, що нульова матриця розміру ~n \times n~ це таблиця чисел, в якій елементи головної діагоналі рівні одиниці, а всі інші рівні нулю. (Головна діагональ містить елементи, у яких номер стовпця співпадає з номером рядка, тобто ~a_{1,1},a_{2,2},a_{3,3}...~).

Допоможіть Халеку і напишіть програму, яка виводить шукану матрицю розміру ~n \times n~.

Input

В єдиному рядку задано одне ціле число n ~(1\le n\le10^3)~.

Output

Виведіть шукану матрицю.

Sample Input 1

4

Sample Output 1

1 0 0 0 
0 1 0 0 
0 0 1 0 
0 0 0 1

Sample Input 2

7

Sample Output 2

1 0 0 0 0 0 0 
0 1 0 0 0 0 0 
0 0 1 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 0 0 1

Після невдалого спілкування з дівчинкою Соньою хлопчик Халек вирішив взятися за голову і почати вчити програмування!

Він вирішив вивчити масиви і натрапив на таку задачу. Дано масив ~a~ з ~n~ цілих чисел. Для кожного префіксу масиву потрібно вивести значення ~max_i - min_i~, де ~max_i~ - це максимум на префіксі ~i~, а відповідно ~min_i~ - мінімум. Знайдіть таке значення для кожного ~i~ ~(1 \le i \le n)~.

Є одна проблемка, Халек ще не вчив ні цикли, ні іфи. Вам потрібно допомогти Халеку, щоб він не розчарувався в програмуванні, як в спілкуванні з дівчатами.

Input

В першому рядку задано одне ціле число ~n~ ~(1 \le n \le 10^6)~.

В наступному рядку задано масив ~a~ - ~n~ цілих чисел ~(-10^9\le a_i \le 10^9)~.

Output

Потрібно вивести через пробіл ~n~ цілих чисел - різницю максимуму і мінімуму на кожному з префіксів.

Sample Input 1

4
-1 3 4 10

Sample Output 1

0 4 5 11

Notes

Префікс - це підмасив, який починається з першого елементу. Тобто декілька елементів, які йдуть підряд з початку масиву.

Цього разу хлопчині на ім'я Халек не до програмування. В університеті розпочалась сесія! У Халека вдома є поличка, на якій лежать ~n~ книжок, в і-тій з них є ~a_i~ сторінок. Хлопчина вирішив готуватись оптимально і виписав t сторінок, які він хоче прочитати. Сторінки він пронумерував наскрізь у всіх книжках, тобто в першій книзі лежать сторінки з номерами ~x_1~ ~(1 \le x_1 \le a_1)~, у другій відповідно ~x_2~ ~(a_1 + 1 \le x_2 \le a_1 + a_2)~ і так далі.

Допоможіть Халеку і для кожної сторінки виведіть номер книги, яка містить цю сторінку.

Input

В першому рядку дано ціле число ~n~ і ~t~ ~(1 \le n \le 10^6)~, ~(1 \le t \le 10^5)~.

В другому рядку дано масив ~a~ - ~n~ цілих чисел ~(1\le a_i \le10^8)~.

В третьому рядку дано масив ~q~ - ~t~ цілих чисел ~(1\le q_i \le 10^{18})~.

Output

Виведіть через пробіл номери всіх шуканих книг, якщо такої книги не існує то виведіть -1.

Sample Input 1

5 4
6 1 9 9 10
32 40 43 14

Sample Output 1

5 -1 -1 3

Sample Input 2

5 4
3 7 9 3 9
21 51 8 16

Sample Output 2

4 -1 2 3

Надихнувшись послідовністю чисел Фібоначчі, Халек вирішив, що він нічим не гірший за Леонарда і вирішив вигадати свою послідовність. Як відомо, завжди легше адаптувати щось старе, ніж придумати нове.

Послідовність Фібоначчі визначається так:

• ~a_1 = 1~
• ~a_2 = 1~
• ~a_{n} = a_{n - 2} + a_{n - 1}, n > 2~

Халек хоче замінити ~a_1~ і ~a_2~ і отримати нову послідовність - послідовність Халека. Але він ще не обрав ці значення. Тому для кожного ~x_i~, ~y_i~, ~n_i~ знайдіть n-те число в послідовності Халека, якщо ~a_1=x_i~, а ~a_2=y_i~. Оскільки число може бути занадто великим, то виведіть остачу від ділення на ~10^9 + 7~.

Input

В першому рядку дано одне ціле число t ~(1\le t \le 10^6)~.

Далі в кожному з t рядків дано 3 цілі числа ~x_i~, ~y_i~, ~n_i~ ~(1 \le x_i, y_i, n_i \le 10^6)~.

Output

Знайдіть для кожного запиту n-те число в послідовності Халека, якщо ~a_1=x_i~, а ~a_2=y_i~, і виведіть їх по модулю ~10^9 + 7~.

Sample Input 1

2
293 713 781
148 983 474

Sample Output 1

7399665
167666110

Sample Input 2

6
8 3 2
9 2 7
10 2 2
1 4 3
10 4 6
1 9 9

Sample Output 2

3
61
2
5
50
202

Нова подруга Халека - Марічка потрапила на вулицю з цукерками. Вона дуже полюбляє солодощі, тому хоче зібрати максимальну кількість цукерок.

Вулиця представлена з n сегментів однакової довжини. В і-тому з них лежить ~a_i~ цукерок. Марічка може стрибати лише на деякі довжини ~b_i~, які задані масивом цілих чисел розміру m.

Оскільки на дворі зима, а як відомо, взимку темніє дуже швидко, Марічка вирішила не баритись і стрибати лише вперед - в напрямку до кінця дороги (тобто якщо Марічка знаходиться на позиції ~x~, то вона може переміститись лише на позицію ~x + b_i~, де ~1\le i\le m~).

Input

В першому рядку дано 1 ціле число - n ~(1\le n \le 10^4)~.

В другому рядку дано n цілих чисел - масив ~a~ ~(1\le a_i \le 10^6)~.

В третьому рядку дано 1 ціле число - m ~(1\le m \le 10^4)~.

В четвертому рядку дано m цілих чисел - масив b ~(1\le b_i \le 10^4~).

Output

Виведіть одне ціле число - найбільшу кількість цукерок, які Марічка зможе зібрати, пересуваючись стрибками розміру ~b_i~.

Sample Input 1

6
10 3 4 4 8 4
4
2 6 3 4

Sample Output 1

12

Notes

Формально Марічка знаходиться на нульовому сегменті, стрибати можна лише довжиною ~b_i~, якщо дівчинка знаходиться в клітині, то вона забирає цукерки з тої клітини. Завершити можна, вистрибнувши за межі ~n~ сегментів.