Każda bramka XOR ma dwa wejścia i jedno wyjście, a jej działanie opisuje następująca tabelka

Siecią XOR nazywamy układ bramek XOR, mający n wejść i jedno wyjście, spełniający następujące warunki:

1. Każde wejście sieci XOR jest połączone z przynajmniej jednym wejściem bramki.
2. Każde wejście każdej bramki jest połączone z jednym wejściem sieci albo z jednym wyjściem innej bramki.
3. Wyjście dokładnie jednej bramki jest połączone z wyjściem sieci.
4. Każde wyjście bramki w sieci jest połączone z przynajmniej jednym wejściem innej bramki - albo z jedynym wyjściem sieci.
5. Istnieje taka numeracja bramek, że do każdego wejścia dowolnej bramki jest podłączone wejście sieci albo wyjście bramki o mniejszym numerze.

Przykład

Przedstawiony na rysunku układ 6 bramek mający 5 wejść i 1 wyjście spełnia warunki 1 - 5, więc jest siecią XOR. Uwaga: bramki na rysunku zostały ponumerowane dowolnie, ale istnieje numeracja spełniająca warunek określony w punkcie 5. Wszystkie wejścia sieci są ponumerowane od 1 do n. Stan wejść sieci XOR opisuje słowo wejściowe utworzone z n cyfr dwójkowych 0 i 1 - przyjmujemy, że i-ta od lewej cyfra danego słowa wejściowego, to stan i-tego wejścia sieci. Dla dowolnego stanu wejść sieć daje na wyjściu 0 albo 1. Każde słowo wejściowe jest dwójkowym zapisem jakiejś liczby naturalnej, więc słowa te można uporządkować zgodnie z ich wartościami liczbowymi. Sieci XOR będziemy testowali podając na wejściu kolejne słowa z ustalonego zakresu i zliczając liczbę otrzymanych w wyniku jedynek.

Zadanie

Napisz program, który:

• wczytuje z pliku tekstowego XOR.IN opis sieci XOR: liczbę wejść n, liczbę bramek m, numer bramki połączonej z wyjściem sieci oraz opisy połączeń, a następnie dwa n-bitowe słowa wejściowe - dolne i górne ograniczenie zakresu, w jakim będziemy testowali sieć,
• oblicza liczbę jedynek otrzymanych na wyjściu sieci dla słów wejściowych z danego zakresu,
• zapisuje wynik w pliku tekstowym XOR.OUT.

Wejście

W pierwszym wierszu pliku tekstowego XOR.IN są zapisane trzy liczby całkowite dodatnie pooddzielane pojedynczym odstępem. Jest to liczba wejść n danej sieci XOR, liczba bramek m oraz numer bramki połączonej z wyjściem sieci. W kolejnych m wierszach znajdują się opisy połączeń bramek sieci. W i-tym z tych wierszy, dla i od 1 do m, znajduje się opis połączeń dwóch wejść bramki o numerze i, który ma postać dwóch liczb całkowitych nie mniejszych niż -n i nie większych niż m, oddzielonych pojedynczym odstępem. Jeśli odpowiednie wejście do bramki jest połączone z wejściem do sieci o numerze k, to opisem tego połączenia jest liczba ujemna -k, a jeśli wejście do bramki jest połączone z wyjściem innej bramki o numerze j, to opisem tego połączenia jest liczba dodatnia j. W kolejnych 2 wierszach pliku tekstowego XOR.IN są zapisane dwa n-bitowe słowa a oraz b. Jest to dolne i górne ograniczenie zakresu testowania sieci. Zakładamy, że w danym zakresie mieści się nie więcej niż sto tysięcy słów.

Wyjście

W pliku tekstowym XOR.OUT należy zapisać jedną liczbę całkowitą nieujemną - liczbę jedynek, jakie powinniśmy otrzymać na wyjściu poprawnie działającej danej sieci XOR dla słów wejściowych s z danego zakresu: a Ł s Ł b, gdzie nierówność Ł należy rozumieć jako relację porządku zgodnego z wartościami liczbowymi słów dwójkowych.

Przykład

Dla pliku XOR.IN, zawierającego opis przedstawionej powyżej sieci XOR:

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

5

Twój program powinien szukać pliku XOR.IN w katalogu bieżącym i tworzyć plik XOR.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę XOR.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku XOR.EXE