XOR 회로

XOR 게이트는 입력 두 개와 출력 하나를 가진다. 동작은 다음 표와 같다.

입력 1   입력 2   출력
  0        0       0
  0        1       1
  1        0       1
  1        1       0

XOR 게이트로 이루어진 회로가 입력 $n$ 개와 출력 하나를 가지며 아래 조건을 모두 만족하면, 이를 XOR 회로라고 부른다.

회로의 모든 입력은 적어도 하나의 게이트 입력에 연결된다.
각 게이트 입력은 회로의 입력 하나 또는 다른 게이트의 출력 하나에 연결된다.
정확히 한 게이트의 출력이 회로의 출력에 연결된다.
각 게이트의 출력은 다른 게이트의 입력 중 적어도 하나, 또는 회로의 출력에 연결된다.
게이트에 번호를 매겨서, 모든 게이트에 대해 그 게이트의 각 입력이 회로의 입력 또는 자신보다 번호가 작은 게이트의 출력에 연결되도록 할 수 있다.

그림은 게이트 $6$ 개로 이루어지고 입력 $5$ 개와 출력 $1$ 개를 가진 회로로, 조건 1부터 5까지를 만족하므로 XOR 회로이다. 그림에 적힌 번호는 조건 5를 만족하지 않지만, 조건 5를 만족하는 번호 매김이 따로 존재한다.

회로의 입력에는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다. XOR 회로의 입력 상태는 길이 $n$ 의 입력 단어로 나타내며, 각 글자는 이진 숫자( $0$ 또는 $1$ )이고 $i$ 번째 글자는 $i$ 번째 입력의 상태이다. 임의의 입력 상태에 대해 회로는 출력으로 $0$ 또는 $1$ 을 낸다. 각 입력 단어는 자연수의 이진 표현이므로 입력 단어들을 그 값에 따라 정렬할 수 있다. 어떤 고정된 구간에 속하는 모든 단어를 회로에 넣고, 그중 출력이 $1$ 이 되는 단어의 개수를 세어 회로를 시험한다.

다음을 수행하는 프로그램을 작성하라.

표준 입력에서 XOR 회로의 정보를 읽는다. 입력 개수 $n$ , 게이트 개수 $m$ , 회로의 출력에 연결된 게이트의 번호, 그리고 연결에 대한 설명이 주어진다.
시험할 구간의 하한과 상한을 나타내는, 길이 $n$ 의 이진 단어 두 개를 읽는다.
그 구간에서 회로의 출력이 $1$ 이 되는 단어의 개수를 계산한다.
그 개수를 표준 출력에 쓴다.

범위는 다음과 같다. $3 \le n \le 100$ 이고 $3 \le m \le 3000$ 이며, 주어진 회로의 게이트에는 $1$ 번부터 $m$ 번까지 임의의 순서로 번호가 매겨져 있다.

첫째 줄에는 공백으로 구분된 정수 세 개가 주어진다. 차례대로 회로의 입력 개수 $n$ , 게이트 개수 $m$ , 회로의 출력에 연결된 게이트의 번호이다.

다음 $m$ 개의 줄에는 각 게이트의 두 입력에 대한 설명이 주어진다. $i$ 번째 줄( $1 \le i \le m$ )에는 $[-n, m]$ 범위의 정수 두 개가 공백으로 구분되어 주어지며, 이는 $i$ 번째 게이트의 두 입력이 어디에 연결되는지를 나타낸다. 어떤 게이트 입력이 회로의 $k$ 번째 입력에 연결되면 음의 정수 $-k$ 로, $j$ 번째 게이트의 출력에 연결되면 양의 정수 $j$ 로 적는다.

그다음 두 줄에는 길이 $n$ 의 이진 단어 $a$ 와 $b$ 가 주어진다. 이는 시험할 구간의 하한과 상한이다. 이 구간에 속하는 단어는 최대 100,000개이다.

문제

입력

출력