

프로그램 P의 처음에 크기 $N$의 배열 $A$가 선언되어 있고,
배열 값 $A[1], A[2], \dots, A[N]$이 모두 0으로
초기화되어있다. 

프로그램 P에는 $M$ 개의 명령이 있다. $i$ 번째 명령은 다음과 같다.

$$
A[X_i] := A[X_i] + A[Y_i] \quad (1 \le i \le M)
$$

여기서, $a := b$는 $a$에 값 $b$를 대입하는 연산이다.

우리는 P를 총 $L$ 번 독립적으로 실행할 것이다.
이때, $j$ 번째 실행에서 각각 $K_j$ 개의 입력값 $U_{j, k}, V_{j, k}$가 주어지고, 이 입력값을 이용해 위의 명령 이전에 다음과 같이 배열의 초기값이 주어진다:
$$
A[U_{j,k}] := V_{j, k} \quad (1 \le k \le K_j)
$$
각 $j$ 번째 실행에서, 주어지는 $U_{j, k}$는 모두 다르다.
또, $U_{j, k}$로 주어지지 않는 $i$에 대해서 $A[i] := 0$임에 주의하자.

프로그램 P의 각각의 실행 뒤, $A[1]$의 값을 구하자.

## 입력 형식

첫 줄에 배열의 크기를 나타내는 $N$,
덧셈 연산을 나타내는 정수 $M$,
실행 횟수를 나타내는 정수 $L$이
공백으로 구분되어 주어진다. ($1 \le N, M, L \le 250\,000$)

이어지는 $M$개 줄의 $i$ 번째 줄에는 $i$ 번째 명령을 정의하는 상수를 나타내는 두 정수 $X_i$와 $Y_i$가 주어진다. ($1 \le X_i, Y_i \le N$)

프로그램의 $L$ 번의 실행을 나타내는 줄들이 순서대로 주어진다. 이 중 $j$ 번째 실행을 나타내는 줄들의 첫 줄에는 입력값의 개수를 나타내는 정수 $K_j$가 주어진다. ($1 \le K_j \le N$)
이어지는 $K_j$ 개의 줄의 $k$ 번째 줄에는 입력값을 나타내는 두 정수 $U_{j, k}$와 $V_{j, k}$가 주어진다.
($1 \le U_{j, k} \le N, 1 \le V_{j, k} \le 1\,000\,000\,000$)

입력값의 총개수인 $\sum K_j$은 $250\,000$ 이하이다. 

## 출력 형식

$L$ 개 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 프로그램의 $i$ 번째 실행 이후, $A[1]$의 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.  

## 입력 예제

```
3 7 2
3 3
3 1
1 2
1 1
1 3
2 1
1 2
2
2 3
3 8
3
1 2
2 6
3 7
```

## 출력 예제

```
47
70
```

## 채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

* 종류 1 (27점): $L \le 500$
* 종류 2 (31점): $N \le 500$
* 종류 3 (42점): 추가적인 제한 조건이 없음.