Masala #D0SAGY5MAK

\(K\)ta mamlakatda jami \(N\)ta shahar bor. Birinchi mamlakatda \(a_1\)ta, ikkinchi mamlakatda \(a_2\)ta, \(K\)-mamlakatda \(a_K\)ta shahar bor va ular ketma-ket raqamlangan. Xususan: 
1-mamlakat shaharlari \(1\)dan \(a_1\)gacha; 
2-mamlakat shaharlari \(a_1+1\)dan \(a_1+a_2\)gacha;
…
K-mamlakat shaharlari \(a_1+a_2+...+a_{K-1} + 1\)dan \(N\)gacha.

Shaharlar orasida harakatlanish uchun yo‘llar qurilgan. Bunda ixtiyoriy \(1 \leq i < N\) uchun \(i\) va \(i+1\)-shaharlar o‘rtasida yo‘l bor. Undan tashqari, \(M\)ta qo‘shimcha yo‘l bir mamlakat ichidagi ikkita shaharni bog‘lab turadi. 

Sizga \(Q\)ta so‘rovda har xil mamlakatda joylashgan \(X\) va \(Y\) shaharlar beriladi. Vazifangiz \(X\) shahardan \(Y\) shaharga boruvchi eng qisqa yo‘llar sonini topish. Javob katta bo‘lib ketishi mumkinligi sababli, javobni \(10^9+7\)ga bo‘lgandagi qoldig‘ini chiqaring.

Birinchi qatorda uchta butun son - \(K, N, M\) sonlari kiritiladi. \((1 \le K, N, M \le 3 \cdot 10^5; K \le N)\)

Ikkinchi qatorda \(a_1,a_2,...,a_K\) beriladi. \((a_i \ge 1; a_1+a_2+...+a_K=N)\)

Keyingi \(M\)ta qatorning har birida ikkitadan butun son - \(u\) va \(v\) beriladi, bu \(u\) va \(v\) shaharlar o‘rtasida qo‘shimcha yo‘l borligini anglatadi. \((1 \le u, v \le N; |u-v| \ge 2)\). Qo‘shimcha yo‘llar bog‘lovchi shaharlar bitta davlatda joylashganligi kafolatlanadi. 

Keyingi qatorda bitta butun son \(Q\) beriladi. \((1 \le Q \le 3 \cdot 10^5)\)

Keyingi \(Q\)ta qatorda \(X\) va \(Y\) shaharlar beriladi. \((1 \le X, Y \le N)\). Bunda ular har xil mamlakatda ekanligi kafolatlanadi.

Har bir so‘rov uchun bitta yangi qatorda so‘rovlarga javobni \(10^9+7\)ga bo‘lingandagi qoldig‘ini chiqaring.