Вам задано натуральне число \(N\) і послідовності з \(N\) натуральних чисел кожна: \(A=(A_1,A_2,\dots,A_N)\) і \(B=(B_1,B_2,\dots,B_N)\).

Ми маємо сітку \(N \times N\). Квадрат у \(i\)-му рядку зверху та \(j\)-му стовпчику зліва називається квадратом (\(i,j\)). Для кожної пари цілих чисел (\(i,j\)), таких що \(1 \le i,j \le N\), квадрат (\(i,j\)) має ціле число \(A_i + B_j\), яке написано на ньому. Обробляйте \(Q\) запити наступної форми.

• Вам дано четвірку цілих чисел \(h_1,h_2,w_1,w_2\) таких, що \(1 \le h_1 \le h_2 \le N\),\(1 \le w_1 \le w_2 \le N\). Знайдіть найбільший спільний дільник цілих чисел, що містяться в області прямокутника, верхній лівий і нижній правий кути якого дорівнюють (\(h_1,w_1\)) і (\(h_2,w_2\)), відповідно.

Обмеження

• \(1 \le N,Q \le 2 \times 10^5\)
• \(1 \le A_i,B_i \le 10^9\)
• \(1 \le h_1 \le h_2 \le N\)
• \(1 \le w_1 \le w_2 \le N\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N, Q\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Третій  рядок містить \(N\) цілих чисел \(B_i\)

Наступні  \(Q\) рядків містять запити: \(h_1, h_2, w_1, w_2\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть в окремому рядку відповідь для кожного запиту.

Примітка

До прикладу 1:

Для 1-го запиту ми маємо \(C_{1,2}=4\),\(C_{1,3}=6\),\(C_{2,2}=6\),\(C_{2,3}=8\), тож відповіддю є їхній найбільший спільний дільник, який дорівнює 2.

Приклад вхідних даних

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Приклад вихідних даних

2
1
11
6
10

Приклад вхідних даних

1 1
9
100
1 1 1 1

Приклад вихідних даних

109