Problema A - O Ábaco

O Alberto é um ávido fã de matemática, e sempre se fascinou por um dos mais antigos instrumentos de cálculo, o ábaco. O ábaco é um intrumento simples mas poderoso; composto por vários arames, cada um segura um número de "pedras" que estão livres para se moverem pelo o arame. Esta estrutura simples permite ao ábaco ajudar, não só com a adição e subtração, mas também multiplicação, divisão e até a raiz quadrada.

Parte I

De tanto passar tempo com ábacos (e com ábacos cada vez maiores), o Alberto quer organizá-los mais facilmente. Uma das características que lhe interessa nos seus ábacos é o número de arames diferentes. Considerando cada arame do seu ábaco como uma semi-recta (uma linha com um começo mas sem fim), eles podem ser descritos pelas posições das suas pedras em relação ao começo do arame. Se dois arames distintos têm o mesmo número de pedras e nas mesmas posições, o Alberto considera que os dois arames são iguais. Consegues ajudá-lo a saber quantos arames diferentes ele tem num dos seus ábacos?

Dado um número N de arames, e para cada arame i, a posição das K_i pedras nesse arame, quantos arames distintos tem o ábaco do Alberto?

Exemplo

Considera o seguinte ábaco com N = 3:

Neste caso o primeiro arame é decrito por: K₁ = 2 pedras, com posições 4 e 7; o segundo por K₂ = 1 pedras, com posição 2, e o terceiro por K₃ = 2, com posições 4 e 7. Como o primeiro e o terceiro arames têm as pedras nas mesmas posições, há dois arames distintos.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

O Alberto tem uma amiga chamada Beatriz que é tão fã de ábacos como ele. Uma das maneiras como se divertem juntos é fazendo corridas de ábacos! Começando com dois ábacos na mesma configuração inicial de pedras, ambos seguem uma lista de movimentos a aplicar a todas as pedras, ora mexendo todas para a esquerda ou direita uma distância d_i. Para poderem garantir que seguiram a lista de instruções corretamente, o Alberto e a Beatriz querem saber qual é a configuração final de um ábaco, dado um conjunto de instruções, e para isso precisam da tua ajuda.

São te dados dois conjuntos de informações, a posição inicial do arame (descrito por N, K_i, e P_ij como na parte anterior) e uma sequência de Q movimentos. Cada movimento é especificado pela direção (E ou D, respetivamente esquerda ou direita) assim como a distância d_i do movimento.

Exemplo

Usando o ábaco da Parte I como posição inicial, consideramos a sequência de movimentos: E 2, E 10 e D 2. A posição das pedras segue a seguinte sequência:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 3 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro N, representando o número de arames do ábaco. No caso da Parte II isto refere-se ao ábaco inicial.

Seguem-se N linhas. A i-ésima linha começa com um inteiro K_i, representando o número de pedras do i-ésimo arame. O valor de K_i é sempre positivo. Seguem-se K_i inteiros separados por espaços, que representam as posições de cada pedra. Estas posições serão dadas por ordem crescente.

Na Parte I isto representa a totalidade o input. Para a Parte II segue-se ainda uma linha com um inteiro Q representando o número de instruções.

Seguem-se Q linhas, a i-ésima contém um par de valores separados por espaços o_i e d_i, onde o_i será o carácter E ou D (que representa a orientação da instrução) e d_i um inteiro que representa a distância da instrução.

Output

Para a Parte I o output deve conter apenas uma linha representando o número de arames distintos.

Para a Parte II o output deve conter N linhas. A i-ésima linha deve conter K_i inteiros separados por espaços e ordenados por ordem crescente, representando as posições finais da pedras do i-ésimo arame.

Input do Exemplo 1

1
3
2 4 7
1 2
2 4 7

Output do Exemplo 1

2

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
3
2 4 7
1 2
2 4 7
3
E 2
E 10
D 2

Output do Exemplo 2

3 4
3
3 4

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.