Masala E

$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.