Dãy số nguyên không âm ~(𝑎_1,𝑎_2,…,𝑎_𝑛)~ được gọi là khớp với dãy số nguyên không âm ~(𝑏_1,𝑏_2,…,𝑏_𝑛)~ qua chuẩn ~𝑀~ nếu ~𝑎_𝑖% 𝑀 = 𝑏_𝑖 % 𝑀~ với mọi ~𝑖 = 1,2,…,𝑛~, trong đó % là phép chia lấy dư.

Với hai dãy số nguyên không âm, việc tìm chuẩn 𝑀 đối với Hoàng không phải là công việc khó, Hoàng còn muốn tìm chuẩn 𝑀 lớn nhất một cách hiệu quả.

Yêu cầu: Cho hai dãy số nguyên không âm ~(𝑎_1,𝑎_2,…,𝑎_𝑛), (𝑏_1,𝑏_2,…,𝑏_𝑛)~ và ~𝑘~ cặp chỉ số ~(𝐿_𝑗,𝑅_𝑗)~ với ~1 ≤ 𝐿_𝑗 ≤ 𝑅_𝑗 ≤ 𝑛, 𝑗 = 1,2,…,𝑘~. Với mỗi cặp chỉ số ~(𝐿_𝑗,𝑅_𝑗)~, hãy tìm số nguyên dương ~𝑀_𝑗~ lớn nhất là chuẩn của hai dãy ~({𝑎𝐿}_𝑗,{𝑎𝐿}_{𝑗+1},…,{𝑎𝑅}_𝑗)~ và ~({𝑏𝐿}_𝑗,{𝑏𝐿}_{𝑗+1},…,{𝑏𝑅}_𝑗)~.

Dữ liệu:

• Dòng đầu chứa số hai số nguyên dương ~𝑛,𝑘 (𝑛 ≤ 10^5);~
• Dòng thứ hai gồm ~𝑛~ số nguyên không âm ~𝑎_1,a_2,…,𝑎_𝑛;~
• Dòng thứ ba gồm ~𝑛~ số nguyên không âm ~𝑏_1,b_2,…,𝑏_𝑛 (𝑏_𝑖 ≠ 𝑎_𝑖 với 𝑖 = 1,2,…,𝑛);~
• Tiếp theo là ~𝑘~ dòng, dòng thứ ~𝑗 (1 ≤ 𝑗 ≤ 𝑘)~ gồm 2 số nguyên dương ~𝐿_𝑗,𝑅_𝑗~ với ~1 ≤ 𝐿_𝑖 ≤ 𝑅_𝑗 ≤ 𝑛, 𝑗 = 1,2,…,𝑘.~

Kết quả: Ghi ra ~𝑘~ dòng, dòng thứ ~𝑗~ là giá trị ~𝑀_𝑗~ lớn nhất là chuẩn của hai dãy ~({𝑎𝐿}_𝑗,𝐿_{𝑗+1},…,{𝑎𝑅}_𝑗)~ và ~({𝑏𝐿}_𝑗,{𝑏𝐿}_{𝑗+1},…,{𝑏𝑅}_𝑗)~.

Chú ý:

• Có 30% số test có ~𝑘 = 1~ và các giá trị ~𝑎_𝑖,𝑏_𝑖~ không vượt quá ~10^3~;
• Có 50% số test khác có 𝑘 ≤ 10 và các giá trị ~𝑎_𝑖,𝑏_𝑖~ không vượt quá ~10^9;~
• Có 20% số test còn lại có ~𝑘 ≤ 10^5~ và các giá trị ~𝑎_𝑖,𝑖~ không vượt quá ~10^{15}~.

Ví dụ:

Input

3 3
1 3 10
10 15 2
1 2
2 3
1 3

Output

3
4
1