Taja passait souvent devant le magasin de jouets et regardait le tableau électronique près de la vitrine qui affichait deux entiers. La vitrine présente plusieurs types de jouets, mais les nombres sur le tableau peuvent être désynchronisés par rapport au nombre réel de types différents. Il s'est avéré que tous les jouets de la vitrine ne peuvent pas être achetés, car ils ne sont pas retirés de la vitrine immédiatement, mais seulement après un certain temps suivant l'achat. Pour différents types de jouets, ce délai peut varier.

Il existe $n$ types de jouets. Pour chaque type de jouet, on connaît la quantité initiale $c_i$ et le temps $t_i$ en minutes après l'achat, au bout duquel le jouet est retiré de la vitrine. Chaque minute, il se passe ce qui suit :

• retrait des jouets de la vitrine qui ont été achetés il y a le nombre de minutes correspondant ;
• le tableau électronique est mis à jour ;
• un nouveau client arrive et achète nécessairement un jouet restant en stock.

Taja a toujours été intéressée par la signification des nombres sur le tableau électronique et elle l'a récemment découverte. Les deux nombres indiquent combien de types de jouets peuvent être achetés dans le magasin, mais le premier indique le nombre de types potentiellement en stock jusqu'au moment actuel, et le second indique le nombre de types qui sont certainement en stock jusqu'au moment actuel. Taja souhaite également savoir à quel point ce tableau est informatif pour les clients. C'est pourquoi elle a besoin d'un programme qui modélisera le comportement des clients et mettra à jour le tableau.

Votre tâche est de calculer les nombres du tableau électronique pour chaque minute.

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 10^5$) — le nombre de types de jouets.

Chacune des $n$ lignes suivantes contient deux entiers $c_i$ et $t_i$ ($1 \le c_i \le 10^5$, $1 \le t_i \le 100$) — le nombre de jouets du $i$-ième type et le temps après lequel le jouet sera retiré de la vitrine après l'achat, respectivement.

La ligne suivante contient un entier unique $k$ ($1 \le k \le 10^5$) — le nombre de clients.

Chacune des $k$ lignes suivantes contient un entier $q_i$ et $q_i$ entiers $p_1, p_2, \dots, p_{q_i}$ — le nombre de jouets retirés à la $i$-ième minute et les numéros de ces jouets.

Sortie

La sortie doit contenir $k$ lignes, chacune contenant deux entiers $a_i$ et $b_i$ — les nombres sur le tableau électronique au début de la $i$-ième minute, respectivement.

Exemples

Entrée 1

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

Sortie 1

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

Remarque

Dans l'exemple ci-dessus, la vitrine contient un jouet du premier type, deux jouets du deuxième type et trois jouets du troisième type, qui sont retirés après 2, 1 et 3 minutes respectivement après l'achat. Les nombres sur le tableau changent dans l'ordre suivant :

• 3/3 : il n'y avait aucun client avant le premier, il peut acheter n'importe quel jouet.
• 3/2 : le premier client a pu acheter le jouet du premier type, il n'y a donc aucune certitude que le deuxième client puisse l'acheter.
• 3/2 : comme aucun jouet du premier ni du deuxième type n'a été retiré de la vitrine, cela signifie que le premier client a acheté le jouet du troisième type. Il est impossible de décider pour l'instant ce qui a été acheté par le deuxième client.
• 2/2 : il n'y a plus de jouets du premier type.
• 2/2 : aucun jouet n'a été retiré de la vitrine, ce qui signifie que le client précédent a acheté un jouet du troisième type.
• 1/1 : il ne reste qu'un seul jouet du troisième type.