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

Nome do arquivo: chefe.x, onde x deve ser c, cpp, java, js ou py

O Chefe

Todos conhecem Iks, a última moda em redes sociais, que fez tanto sucesso que competidores como Facebook e Google+ estão começando a ter dificuldades financeiras. Assim como muitas companhias ".com", Iks surgiu em uma pequena garagem, mas hoje emprega milhares de pessoas no mundo todo.

O sistema de gerência utilizado em Iks é bem diferente do padrão. Por exemplo, não há diretorias ou superintendências. No entanto, como é usual em outras companhias, há uma cadeia (ou melhor, várias cadeias) de comando: uma pessoa pode gerenciar outras pessoas, e pode ser gerenciada por outras pessoas. As figuras abaixo mostram a cadeia de comando para alguns empregados, junto com suas idades.

Uma pessoa P1 pode gerenciar outra pessoa P2 diretamente (quando P1 é o superior imediato de P2) ou indiretamente (quando P1 gerencia diretamente uma pessoa P3 que gerencia P2 direta ou indiretamente). Por exemplo, na figura (a) acima, Alice gerencia David diretamente e Clara indiretamente. Uma pessoa não gerencia a si própria, nem direta nem indiretamente.

Um folclore que apareceu em Wall Street é que Iks é tão bem sucedido porque em sua rede de comando um(a) gerente é sempre mais jovem do que as pessoas que ele(a) gerencia. Como podemos ver na figura acima, isso não é verdade. Mas esse folclore incentivou Iks a desenvolver uma ferramenta para analisar o seu sistema de gerenciamento, e estudar se tem alguma influência no sucesso da empresa. Você foi contratado para trabalhar nessa ferramenta.

Dadas a descrição da cadeia de comando na Iks e as idades de seus empregados, escreva um programa que execute uma série de instruções. Instruções podem ser de dois tipos: trocas de gerência e perguntas. Uma instrução de troca de gerência faz dois empregados A e B trocarem suas posições na cadeia de comando. Como exemplo, a figura (b) acima mostra a cadeia de comando resultante quando David e George trocam suas respectivas posições na cadeia de comando. Uma instrução de pergunta identifica um empregado A e deseja saber a idade do mais jovem gerente (direto ou indireto) de A na cadeia de comando. Por exemplo, no cenário da figura (a) acima a idade do(a) gerente mais jovem de Clara é 18 anos; já no cenário da figura (b), a idade do(a) gerente mais jovem de Clara é 21 anos.

Entrada

A entrada é composta de várias linhas. A primeira linha contém três inteiros N, M e I, indicando respectivamente o número de empregados, o número de relações de gerência direta e o número de instruções. Empregados são identificados por números de 1 a N. A segunda linha contém N inteiros Ki, onde Ki indica a idade do empregado de número i.

Cada uma das M linhas seguintes contém dois inteiros X e Y, indicando que X gerencia Y diretamente. Seguem-se I linhas, cada uma descrevendo uma instrução. Uma instrução de troca de gerência é descrita em uma linha contendo o identificador T seguido de dois inteiros A e B, indicando os dois empregados que devem trocar seus lugares na cadeia de comando. Uma instrução de pergunta é descrita em uma linha contendo o identificador P seguido de um inteiro E , indicando um empregado. A última instrução será sempre do tipo pergunta.

Saída

Para cada instrução de pergunta seu programa deve imprimir uma linha contendo um único inteiro, a idade da pessoa mais jovem que gerencia (direta ou indiretamente) o empregado nomeado na pergunta. Se o empregado nomeado não possui um gerente, imprima o caractere ‘*’ (asterisco).

Restrições

  • 1 ≤ N ≤ 500
  • 0 ≤ M ≤ 60 \times 103
  • 1 ≤ I ≤ 500
  • 1 ≤ Ki ≤ 100, para 1 ≤ i ≤ N
  • 1 ≤ X,Y ≤ N, X ≠ Y
  • 1 ≤ A,B ≤ N
  • 1 ≤ E ≤ N

Exemplos

Entrada
7 8 9
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
P 7
T 4 2
P 7
P 5
T 1 4
P 7
T 4 7
P 2
P 6
Saída
18
21
18
18
*
26
	

 

Entrada
6 5 6
10 20 30 40 50 60
1 5
1 4
3 6
2 5
4 5
P 1
P 5
P 6
T 1 6
P 1
P 4
Saída
*
10
30
30
60
	

 

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