Тая часто проходила мимо магазина игрушек и смотрела на электронное табло рядом с витриной, на котором отображались два целых числа. Витрина магазина демонстрирует несколько видов игрушек, но числа на табло могут не совпадать с фактическим количеством видов, доступных в данный момент. Оказалось, что не каждую игрушку с витрины можно купить сразу, так как их убирают не мгновенно, а спустя некоторое время после покупки. Для разных видов игрушек это время может различаться.

Всего существует $n$ видов игрушек. Для каждого вида известно начальное количество игрушек $c_i$ и время $t_i$ в минутах после покупки, по истечении которого игрушка убирается с витрины. Каждую минуту происходит следующее:

• удаление с витрины игрушек, которые были куплены соответствующее количество минут назад;
• обновление электронного табло;
• приходит новый покупатель и обязательно покупает какую-то игрушку, которая есть в наличии.

Таю всегда интересовало значение чисел на электронном табло, и недавно она его выяснила. Оба числа показывают, сколько видов игрушек можно купить в магазине, но первое число показывает количество видов, которые потенциально могут быть в наличии к текущему моменту, а второе — количество видов, которые точно находятся в наличии к текущему моменту. Тае также интересно, насколько это табло информативно для покупателей. Поэтому ей нужна программа, которая будет моделировать поведение покупателей и обновлять табло.

Ваша задача: для каждой минуты вычислить числа на электронном табло.

Входные данные

Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 10^5$) — количество видов игрушек.

Каждая из следующих $n$ строк содержит два целых числа $c_i$ и $t_i$ ($1 \le c_i \le 10^5$, $1 \le t_i \le 100$) — количество игрушек $i$-го вида и время, через которое игрушка будет убрана с витрины после покупки соответственно.

Следующая строка содержит единственное целое число $k$ ($1 \le k \le 10^5$) — количество покупателей.

Каждая из следующих $k$ строк содержит целое число $q_i$ и $q_i$ целых чисел $p_1, p_2, \dots, p_{q_i}$ — количество игрушек, которые были удалены в $i$-ю минуту, и номера этих игрушек.

Выходные данные

Выведите $k$ строк, каждая из которых содержит два целых числа $a_i$ и $b_i$ — числа на электронном табло в момент начала $i$-й минуты соответственно.

Примеры

Пример 1

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

Выходные данные 1

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

Примечание

В приведенном выше примере на витрине магазина находится одна игрушка первого вида, две игрушки второго вида и три игрушки третьего вида, которые убираются через 2, 1 и 3 минуты соответственно после покупки. Числа на табло должны меняться в следующем порядке:

• 3/3: до первого покупателя клиентов не было, он может купить любую игрушку.
• 3/2: первый покупатель мог купить игрушку первого вида, поэтому нет уверенности, что второй покупатель сможет её купить.
• 3/2: так как ни игрушка первого, ни второго вида не были удалены с витрины, это означает, что первый покупатель купил игрушку третьего вида. Что купил второй покупатель, пока определить невозможно.
• 2/2: игрушек первого вида больше нет.
• 2/2: ни одна игрушка не была удалена с витрины, что означает, что предыдущий покупатель купил игрушку третьего вида.
• 1/1: осталась только одна игрушка третьего вида.