Taja a menudo pasaba por la juguetería y miraba la tabla electrónica cerca del escaparate, la cual mostraba dos números enteros. El escaparate muestra varios tipos de juguetes, pero los números en la tabla pueden no estar sincronizados con la cantidad real de los diferentes tipos. Resultó que no todos los juguetes del escaparate pueden comprarse, ya que no retiran los juguetes tan pronto como es posible, sino solo después de que ha pasado cierto tiempo desde la compra. Para diferentes tipos de juguetes, este tiempo puede ser distinto.

Existen $n$ tipos de juguetes. Para cada tipo de juguete se conoce la cantidad inicial de juguetes $c_i$ y el tiempo $t_i$ en minutos después de la compra, tras el cual el juguete se retira del escaparate. Cada minuto ocurre lo siguiente:

• se retiran del escaparate los juguetes que fueron comprados hace la cantidad correspondiente de minutos;
• la tabla electrónica se actualiza;
• llega un nuevo cliente y necesariamente compra algún juguete que queda en existencia.

Taja siempre ha estado interesada en el significado de los números en la tabla electrónica y recientemente lo descubrió. Ambos números muestran cuántos tipos de juguetes se pueden comprar en la tienda, pero el primero muestra el número de tipos que posiblemente están en existencia hasta el momento actual, y el segundo es el número de tipos que están en existencia hasta el momento actual con seguridad. Además, a Taja le interesa qué tan informativa es esta tabla para los clientes. Por eso necesita un programa que modele el comportamiento de los clientes y actualice la tabla.

Tu tarea es: para cada minuto, calcular los números de la tabla electrónica.

Entrada

La primera línea de la entrada contiene un único número entero $n$ ($1 \le n \le 10^5$) — el número de tipos de juguetes.

Cada una de las siguientes $n$ líneas contiene dos números enteros $c_i$ y $t_i$ ($1 \le c_i \le 10^5$, $1 \le t_i \le 100$) — la cantidad de juguetes del $i$-ésimo tipo y el tiempo, después del cual el juguete será retirado del escaparate tras la compra, respectivamente.

La siguiente línea contiene un único número entero $k$ ($1 \le k \le 10^5$) — el número de clientes.

Cada una de las siguientes $k$ líneas contiene un número entero $q_i$ y $q_i$ números enteros $p_1, p_2, \dots, p_{q_i}$ — la cantidad de juguetes que fueron retirados en el $i$-ésimo minuto y los números de estos juguetes.

Salida

La salida debe contener $k$ líneas, cada una de las cuales contiene dos números enteros $a_i$ y $b_i$ — los números en la tabla electrónica al momento del inicio del $i$-ésimo minuto, respectivamente.

Ejemplos

Entrada 1

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

Salida 1

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

Nota

En el ejemplo anterior, el escaparate contiene un juguete del primer tipo, dos juguetes del segundo tipo y tres juguetes del tercer tipo, los cuales se retiran después de 2, 1 y 3 minutos respectivamente tras la compra. Los números en la tabla cambian en el siguiente orden:

• 3/3: no había clientes antes del primero, él puede comprar cualquier juguete.
• 3/2: el primer cliente podría posiblemente comprar el juguete del primer tipo, por lo tanto, no hay certeza de que el segundo cliente pueda comprarlo.
• 3/2: dado que no se ha retirado del escaparate ningún juguete del primer ni del segundo tipo, significa que el primer cliente compró el juguete del tercer tipo. Aún es imposible decidir qué compró el segundo cliente.
• 2/2: ya no quedan juguetes del primer tipo.
• 2/2: no se ha retirado ningún juguete del escaparate, lo que significa que el cliente anterior compró un juguete del tercer tipo.
• 1/1: solo queda un juguete del tercer tipo.