28a Olimpíada Brasileira de Informática
Submeta sua solução

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.
Por exemplo, considere a família mostrada na figura ao lado, com 10 matriarcas, identificadas pelos números de 1 a 10, com 1 sendo a matriarca mais velha. A fortuna de cada matriarca está indicada ao lado dela, em milhões de reais.
Se a matriarca 2 convocar uma reunião e definir o intervalo de fortunas como [4, 10], as matriarcas convocadas serão 1, 2, 3, 5, 6, 8 e 9. Observe que a matriarca 4 não será convocada pois possui fortuna igual a 3 (menor do que o limite inferior 4).
Por outro lado, uma reunião convocada pela matriarca 8 com o intervalo de fortunas [4, 9] terá as matriarcas 2, 6, 8 e 9. Apesar de a matriarca 5 possuir fortuna no intervalo [4, 9], ela não foi convocada pois não possui relação de parentesco direto com nenhuma outra matriarca convocada.
Sua tarefa é: dada a estrutura da família, a fortuna de cada matriarca, e quem convocou e os limites de fortuna de cada reunião, determine para quantas reuniões cada matriarca foi 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.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

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
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação