Rozważmy zbiór wszystkich możliwych multizbiorów nad zbiorem liczb naturalnych. Definiujemy dwa operatory dla tak określonej dziedziny:

- |E,e|, obcięcie multizbioru E do pierwszych e elementów zapisanych w kolejności niemalejącej, np.

 |{0,3,2,2,0} , 3| = |{0,0,2,2,3},3| = {0,0,2},

- [E,F,G,e], suma alternatywna z obcięciem multizbiorów E oraz F, albo E oraz G, taka, że:

 [E,F,G,e]=|E+F,e|, jeżeli suma elementów multizbioru E jest parzysta,

[E,F,G,e]=|E+G,e|, jeżeli suma elementów multizbioru E jest nieparzysta,

gdzie + jest klasycznym operatorem sumy multizbiorów, np.

[{0,2},{1,2},{0,3},3]=|{0,2}+{1,2},3|=|{0,2,1,2},3|=|{0,1,2,2},3|={0,1,2}.

Dalej jest X={x(0), x(1), …, x(n-1)} jest rodziną n niepustych multizbiorów nad zbiorem liczb naturalnych oraz m jest pewną ustaloną dodatnią liczbą naturalną. Wyznacz sumę elementów multizbioru będącego rezultatem k-krotnego złożenia operatora sumy alternatywnej z obcięciem na zbiorze pustym {}, takiego, że

[…[[{},x(i_0),x(j_0),m],x(i_1),x(j_1),m]…,x(i_(k-1)),x(j_(k-1)),m],

gdzie 0<=i_p,j_q<n, dla 0<=p,q<k. Dodatkowo podaj liczbę różnych elementów multizbioru będącego rezultatem tego złożenia.



WEJŚCIE

Wiersz zawierający liczby n, m oraz k oddzielone znakiem odstępu (kod ASCII 32) i zakończony znakiem nowej linii (kod ASCII 10). Następnie n wierszy reprezentujących elementy kolejnych multizbiorów x(i), dla 0<=i<n, poprzedzone liczbą określającą rozmiar danego multizbioru oraz znakiem odstępu. Elementy wierszy rozdzielone są znakiem odstępu, a każdy wiersz zakończony jest znakiem nowej linii. Dalej k wierszy reprezentujący pary indeksów multizbiorów należących do rodziny X odpowiadające kolejności ich występowania w rozważanym złożeniu operatora sumy alternatywnej z obcięciem (czytane od lewej do prawej strony). Elementy wierszy rozdzielone są znakiem odstępu, a każdy wiersz zakończony jest znakiem nowej linii.


WYJŚCIE

Wiersz zawierający dwie liczby naturalne oddzielone znakiem odstępu stanowiące rozwiązanie problemu.

OGRANICZENIA

Liczby n i m zawarte w przedziałach odpowiednio [1,10^3] i [1,10^7].  Krotność k analizowanego złożenia ograniczona od dołu przez 1 i od góry przez 10^7. Rozmiar multizbiorów z rodziny X oraz wartość maksymalnego elementu należącego do wymienionych multizbiorów ograniczone przedziałami kolejno [1,10^4] i [0,10^7].


LIMITY

Złożoność czasowa i pamięciowa ograniczone możliwością poprawnego wykonania rozwiązania na platformie SPOX :-)

PRZYKŁAD 1

wejście:

3 5 4

1 1
5 0 8 5 8 9
5 1 0 3 1 2
0 1
1 0
0 2
2 1

wyjście:

8 3

KOMENTARZ DO ROZWIĄZANIA

Zgodnie z danymi wejściowymi zachodzi

x(0)={1}

x(1)={0,8,5,8,9}

x{2}={1,0,3,1,2}

Dalej, rozważane 4 krotne złożenie operatora sumy alternatywnej z obcięciem na zbiorze pustym, gdzie m=5, ma postać:

krok nr 1: [{},x{0},x{1},5]=|{}+x{0},5|={1}

krok nr 2: [{1},x{1},x{0},5]=|{1}+x{0},5|={1,1}

krok nr 3: [{1,1},x{0},x{2},5|=|{1,1}+x{0},5|={1,1,1}

krok nr 4: [{1,1,1},x{2},x{1},5|=|{1,1,1}+x{1},5|=|{0,1,1,1,5,8,8,9},5|={0,1,1,1,5}

Stąd suma elementów multizbioru będącego rezultatem rozważanego złożenia jest równa 8, a sam multizbiór składa się z elementów o trzech różnych wartościach.

Zatem odpowiedź stanowi dwójka liczb 8 oraz 3.

PRZYKŁAD 2

wejście:

6 10 10

7 9 9 7 3 9 3 1
4 6 8 5 2
7 8 6 9 6 7 3 1
4 1 9 0 3
9 9 8 8 8 6 4 3 3 6
4 1 9 5 6
1 3
1 4
1 4
0 4
5 4
3 4
1 5
4 1
4 5
5 4

wyjście:

22 3

PRZYKŁAD 3

wejście:

12 20 20

20 1 8 4 5 8 7 3 8 3 1 4 1 2 9 3 9 3 8 4 6
4 2 2 7 2
16 0 1 9 1 8 7 4 1 7 7 5 9 9 5 2 1
20 7 6 4 0 8 1 3 9 8 1 8 7 3 6 6 9 5 9 6 6
15 7 4 2 7 9 6 7 6 3 9 8 3 5 8 0
12 1 4 9 1 9 8 9 5 0 6 7 9
12 5 2 1 6 7 2 9 4 9 4 5 9
7 3 7 9 6 9 8 8
9 8 1 7 9 9 4 8 7 5
10 6 1 2 0 2 0 2 1 0 7
3 5 1 8
1 0
1 11
7 1
2 5
8 6
11 0
9 9
7 9
4 1
0 3
5 10
9 7
6 10
9 3
8 9
5 1
2 10
8 8
7 2
9 1
6 4

wyjście:

0 1