While on a journey in search of her mother's home, Mayoi Hachikuji continuously finds herself lost within the massive network of roads of her city.

In this city, there are ~N~ intersections labelled ~1~ to ~N~, joined by ~M~ directed roads. Being the curious child she is, Mayoi would like to ask you ~Q~ queries about this large and mysterious city.

With her past experience in life leading her to avoid as many trucks as possible, Mayoi asks you the following question:

If I start at intersection ~C_l~ and take at most ~K_l~ steps, what is the minimal number of passing trucks per minute (denoted by ~A_i~), over all the intersections I could possibly traverse (denoted by ~c~)?

Being a ghost who cannot pass through walls, Mayoi asks you a second question to help her save time:

For the same starting intersection ~C_l~, at how many possible different intersections could I finish my journey by taking exactly ~K_l~ steps (denoted by ~d~)?

Note: If Mayoi finds herself at an intersection with no outgoing roads and has yet to take exactly ~K_l~ steps, she will leave (as such, the intersection will not count as a destination intersection.

Input Specification

The first line of input contains two space-separated integers ~N~ and ~M~, representing the number of intersections and the number of roads which join these intersections respectively.

The second line contains ~N~ space separated integers ~A_i~ ~(1 \le i \le N)~, representing the number of trucks which pass through the intersection every minute.

The next ~M~ lines will each contain two space separated integers ~u_j~ and ~v_j~ ~(1 \le j \le M)~, denoting a directed road from the intersection numbered ~u_j~ to the one numbered ~v_j~.

The next line of input contains the integer ~Q~, representing the number of queries from Mayoi.

The next ~Q~ lines will each contain two space separated integers ~C_l~ and ~K_l~ ~(1 \le l \le Q)~.

Constraints

For all subtasks:

~0 \le M \le N^2~

~0 \le A_i \le 1000~

~1 \le u_j, v_j, C_l \le N~

Subtask	Points	~N~	~Q~	~K_l~
~1~	~10\%~	~1 \le N \le 50~	~0 \le Q \le 100~	~0 \le K_l \le N~
~2~	~10\%~	~1 \le N \le 500~	~0 \le Q \le 100~	~0 \le K_l \le N~
~3~	~80\%~	~1 \le N \le 500~	~0 \le Q \le 1000~	~0 \le K_l \le 10^9~

Output Specification

For each of Mayoi's queries, output the desired answers (~c~ and ~d~) to her questions as two space-separated integers on a single line: c d.

Sample Input 1

3 2
3 1 2
1 2
3 1
4
1 0
3 0
3 1
3 3

Sample Output 1

3 1
2 1
2 1
1 0

Explanation 1

The graph of Sample Input ~1~ is shown above, with the rate of passing trucks displayed in red.

For Mayoi's first two queries, she does not take any steps. Therefore, the minimum rate of passing trucks is that of the starting intersection. The starting point is also the only possible destination point.

For her last query, the intersection with the lowest rate of trucks ~\le 3~ steps away from the start is intersection #~2~, with a rate of ~1~. There are no intersections exactly ~3~ steps away from intersection #~3~, so the number of possible destination intersections is ~0~.

Sample Input 2

4 4
5 7 3 8
4 1
2 3
2 4
3 1
2
2 1
4 4

Sample Output 2

3 2
5 0