Dãy số nguyên không âm (𝑎₁,𝑎₂,…,𝑎_𝑛) được gọi là khớp với dãy số nguyên không âm (𝑏₁,𝑏₂,…,𝑏_𝑛) 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 (𝑎₁,𝑎₂,…,𝑎_𝑛), (𝑏₁,𝑏₂,…,𝑏_𝑛) 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: Vào từ file văn bản seq.inp có định dạng:

• Dòng đầu chứa số hai số nguyên dương 𝑛,𝑘 (𝑛 ≤ 10⁵);
• Dòng thứ hai gồm 𝑛 số nguyên không âm 𝑎₁,₂,…,𝑎_𝑛;
• Dòng thứ ba gồm 𝑛 số nguyên không âm 𝑏₁,₂,…,𝑏_𝑛 (𝑏_𝑖 ≠ 𝑎_𝑖 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³;
• Có 50% số test khác có 𝑘 ≤ 10 và các giá trị 𝑎_𝑖,𝑏_𝑖 không vượt quá 10⁹;
• Có 20% số test còn lại có 𝑘 ≤ 10⁵ và các giá trị 𝑎_𝑖,_𝑖 không vượt quá 10¹⁵.