XOR Gates

Memory limit: 32 MB

A XOR gate has two inputs and one output. Its operation can be described by the following table

input 1   input 2    output
   0         0          0
   0         1          1
   1         0          1
   1         1          0

A system of XOR gates is called a XOR net if it has inputs and one output and meets the following conditions:

1. Each input of the net is connected to at least one input of a gate.
2. Each input of a gate in the net is connected to one input of the net or one output of another gate.
3. The output of exactly one gate is connected to output of the net.
4. Each output of a gate in the net is connected to at least one input of another gate, or to the output of the net.
5. There exists a numbering of gates such that for every gate each of its inputs is connected to the input of the net or to the output of a gate with a smaller number.

Example

The net of gates is shown in the figure. It has inputs and output and meets conditions 1–5 so it is a XOR net. Observe that the numbers given in the figure do not agree with the fifth condition but there exists an appropriate numbering.

Inputs of a net are numbered from to . An input state of a XOR net can be described by an input word of the length . Each letter of such a word is a binary digit or . We assume that -th digit of the word is a state of the -th input of the net. For every input state the net returns or on its output. Each input word is a binary code of a natural number so we can order input words with respect to their values. We will test XOR nets by sending words from a fixed range to its input and counting the number of digits 1 returned on the output of the net.

Task

Write a program that:

• reads the description of a XOR net from the standard input; the descriptions consists of: the number of inputs , the number of gates , the number of the gate connected to the output of the net and descriptions of connections;
• reads from the same file two binary words of length — lower and upper limit of the range in which we will test the net;
• computes for how many inputs from the given range the net returns 1 on its output;
• writes the result to the standard output.

We assume that: , and that the gates of the given net are numbered from to in an arbitrary order.

Input

In the first line of the standard input there are three integers separated by single spaces. They are respectively: the number of inputs of the given net, the number of gates and the number of the gate connected to the output of the net.

In the following lines there are descriptions of the connections between gates of the net. In the -th line, for , there is a description of the connections of two inputs of the -th gate. Such a description consists of two integers from the range separated by a single space. If an input of the gate is connected to the -th input of the net then the description of this connection is the negative integer , if this input is connected to the output of the -th gate then it is described by the positive number .

In the following two lines there are two -bit words and . They represent lower and upper limits of the range in which we test the net. We assume that in the given range there is at most words.

Output

In the standard output there should be written a single non-negative integer — the number of words from the range (where is the relation consistent with the values of binary words), for which the XOR net returns 1 on its output.

Example

For the input data:

5 6 5
-1 -2
1 3
1 -2
2 -3
4 6
-4 -5
00111
01110

the correct result is:

5

Task author: Tomasz Smigielski.