由于 Wulala 在上个问题中的精彩表现，公主认为 Wulala 是一个很棒的人，就把 Wulala 留在 了 X 国。这时正好公主的一位传教士朋友来拜访公主，于是想找 wulala 帮忙 X 国如同一条直线，其中有 n 个城市,从东向西分别编号为 1~n。而他的国家中有 m 种宗教， 每个城市一定会有一种信仰的宗教。 有时候有些城市为了获得更多的认可，会派出信仰本城市宗教的传教士前往其他国家。X 国 的传教士都十分厉害，只要是他途经的地方都会改信他所传播的宗教。 传教士们在路上碰到自己宗教的城市自然就不用传教了，可以停下来看看里番啥的，所以每 一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。 而传教士们都是文科僧，数学是很差的，所以他希望 Wulala 能帮他计算。可 Wulala 数学也 不好，但他又不想在公主面前丢脸，你能帮帮他吗？

第一行两个整数 n，m 第二行 n 个整数第 i 个整数代表第 i 各城市信仰的宗教 第三行一个整数 T 代表传教士的个数 接下来 T 行每行两个整数 x，y 代表 x 城向 y 城派遣了一个传教士(保证 x < y)

输出 T 行，第 i 行代表第 i 个传教士询问的答案

2 2
1 2
2
1 2
1 2

0
1