28a Olimpíada Brasileira de Informática
Fortunas
A família Silva tem a tradição de investir em grandes empreendimentos. A família é um matriarcado, ou seja, são as mulheres da família que comandam as decisões. Vamos chamar de matriarca cada mulher integrante da família. Elas são sócias de empresas como bancos, mineradoras, construtoras e petroleiras. Além de saberem analisar muito bem diversos setores da economia, elas são muito unidas e investem sempre de maneira conjunta, em família. Apesar de investirem juntas, cada matriarca da família possui sua própria fortuna e administra seu próprio patrimônio. Um detalhe curioso é que, nessa família, a fortuna de uma matriarca é sempre menor que a fortuna de sua mãe, como consequência da experiência administrativa dos mais velhos. Toda vez que uma matriarca da família pretende investir em algum empreendimento novo, ela convoca uma reunião com outras matriarcas para compartilhar conhecimento. Quando uma matriarca V convoca uma reunião, ela define um intervalo [E, D] de valores de fortunas, de modo que são convocadas todas as matriarcas da família que satisfazem as seguintes condições:- A matriarca V é convocada para sua própria reunião (chamamos ela de anfitriã), e é garantido que sua fortuna está no intervalo [E, D] (ou seja, sua fortuna é maior ou igual a E e menor ou igual a D);
- Toda matriarca convocada precisa ter fortuna no intervalo [E, D];
- Toda matriarca convocada além da anfitriã precisa ter relação de parentesco direto (ou seja, ser mãe ou filha imediata) com alguma outra matriarca convocada.



Entrada
A primeira linha de entrada contém dois inteiros N e M representando o número de matriarcas da família e o número de reuniões, respectivamente. As matriarcas da família são identificadas por inteiros de 1 a N, com o número 1 representando a matriarca mais velha da família. As próximas N linhas descrevem a estrutura da família. A i-ésima dessas linhas contém dois inteiros Ai e Bi representando a fortuna da i-ésima matriarca e o identificador de sua mãe, respectivamente. A matriarca mais velha da família (matriarca 1) é a única matriarca com Bi = i. É garantido que a fortuna de uma matriarca é sempre menor que a fortuna de sua mãe. As próximas M linhas descrevem as reuniões. A j-ésima dessas linhas contém três inteiros Oj, Ej e Dj, indicando que a matriarca Oj foi anfitriã de uma reunião com intervalo de fortunas [Ej, Dj].Saída
Seu programa deverá imprimir uma única linha contendo N inteiros separados por espaços. O i-ésimo desses números deve ser a quantidade de reuniões para as quais a matriarca i foi convocada.Restrições
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- 1 ≤ Ai ≤ 100 000
- Ai < A_{Bi} para todo i>1
- 1 ≤ Bi ≤ N
- 1 ≤ Oj ≤ N
- 1 ≤ Ej ≤ A_{Oj} ≤ Dj ≤ 100 000
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:- Subtarefa 1 (13 pontos): M = 1
- Subtarefa 2 (21 pontos): Bi = i-1 para todo i>1 -- ou seja, a mãe da matriarca i é a matriarca i - 1. (Veja o exemplo de entrada 2.)
- Subtarefa 3 (25 pontos): Ej = 1 e Dj = A_{Oj} para todo 1 ≤ j ≤ M
- Subtarefa 4 (21 pontos):
- Dj = A_{Oj} para todo 1 ≤ j ≤ M
- Ai ≤ 200 para todo 1 ≤ i ≤ N
- Subtarefa 5 (20 pontos): Nenhuma restrição adicional.
Exemplos
Entrada
10 2 10 1 8 1 5 5 3 1 6 1 4 8 1 5 7 2 5 8 2 8 2 4 10 8 4 9 |
Saída
1 2 1 0 1 2 0 2 2 0 |
Entrada
8 5 42 1 31 1 29 2 27 3 18 4 15 5 12 6 5 7 1 17 42 4 18 30 8 5 28 4 16 40 6 12 18 |
Saída
1 2 3 4 5 2 2 1 |