XOR 회로

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

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

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

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

그림은 게이트 $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개이다.

표준 출력에 음이 아닌 정수 하나를 출력한다. 이는 $a \le s \le b$(순서는 이진 단어의 값을 기준으로 한다)를 만족하는 단어 $s$ 중에서 XOR 회로의 출력이 $1$이 되는 단어의 개수이다.