Taja często przechodziła obok sklepu z zabawkami i spoglądała na elektroniczną tablicę umieszczoną przy witrynie, na której wyświetlane były dwie liczby całkowite. Witryna sklepowa prezentuje kilka rodzajów zabawek, ale liczby na tablicy mogą nie zgadzać się z faktyczną liczbą dostępnych rodzajów. Okazało się, że nie każdą zabawkę z witryny można kupić, ponieważ zabawki nie są usuwane z wystawy natychmiast po zakupie, lecz dopiero po upływie pewnego czasu. Dla różnych rodzajów zabawek czas ten może być inny.

Istnieje $n$ rodzajów zabawek. Dla każdego rodzaju zabawki znana jest początkowa liczba sztuk $c_i$ oraz czas $t_i$ (w minutach) od momentu zakupu, po którym zabawka jest usuwana z witryny. W każdej minucie dzieje się co następuje:

• usuwane są z witryny zabawki, które zostały zakupione odpowiednią liczbę minut temu;
• elektroniczna tablica jest aktualizowana;
• pojawia się nowy klient, który obowiązkowo kupuje jedną zabawkę spośród tych, które pozostały w magazynie.

Taja zawsze interesowała się znaczeniem liczb na elektronicznej tablicy i niedawno je odkryła. Obie liczby wskazują, ile rodzajów zabawek można kupić w sklepie, przy czym pierwsza z nich oznacza liczbę rodzajów, które potencjalnie mogą być w magazynie do bieżącej chwili, a druga to liczba rodzajów, które na pewno są w magazynie do bieżącej chwili. Taja jest również ciekawa, na ile ta tablica jest informatywna dla klientów. Dlatego potrzebuje programu, który będzie modelował zachowanie klientów i aktualizował tablicę.

Twoim zadaniem jest obliczenie liczb na elektronicznej tablicy dla każdej minuty.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 10^5$) — liczbę rodzajów zabawek.

Każda z kolejnych $n$ linii zawiera dwie liczby całkowite $c_i$ oraz $t_i$ ($1 \le c_i \le 10^5$, $1 \le t_i \le 100$) — odpowiednio liczbę zabawek $i$-tego rodzaju oraz czas, po którym zabawka zostanie usunięta z witryny po zakupie.

Następna linia zawiera pojedynczą liczbę całkowitą $k$ ($1 \le k \le 10^5$) — liczbę klientów.

Każda z kolejnych $k$ linii zawiera liczbę całkowitą $q_i$ oraz $q_i$ liczb całkowitych $p_1, p_2, \dots, p_{q_i}$ — liczbę zabawek, które zostały usunięte w $i$-tej minucie oraz numery tych zabawek.

Wyjście

Wyjście powinno zawierać $k$ linii, z których każda zawiera dwie liczby całkowite $a_i$ oraz $b_i$ — liczby na elektronicznej tablicy w momencie początku $i$-tej minuty.

Przykład

Wejście 1

3
1 2
2 1
3 3
6
0
0
0
3 1 2 3
0
1 2

Wyjście 1

3 3
3 2
3 2
2 2
2 2
1 1

Uwagi

W powyższym przykładzie witryna sklepowa zawiera jedną zabawkę pierwszego rodzaju, dwie zabawki drugiego rodzaju i trzy zabawki trzeciego rodzaju, które są usuwane odpowiednio po 2, 1 i 3 minutach od zakupu. Liczby na tablicy powinny zmieniać się w następującej kolejności:

• 3/3: przed pierwszym klientem nie było żadnych klientów, może on kupić dowolną zabawkę.
• 3/2: pierwszy klient mógł potencjalnie kupić zabawkę pierwszego rodzaju, więc nie ma pewności, że drugi klient będzie mógł ją kupić.
• 3/2: skoro z witryny nie została usunięta zabawka ani pierwszego, ani drugiego rodzaju, oznacza to, że pierwszy klient zakupił zabawkę trzeciego rodzaju. O tym, co zakupił drugi klient, nie da się jeszcze zdecydować.
• 2/2: brak zabawek pierwszego rodzaju.
• 2/2: żadna zabawka nie została usunięta z witryny, co oznacza, że poprzedni klient kupił zabawkę trzeciego rodzaju.
• 1/1: pozostała tylko jedna zabawka trzeciego rodzaju.