Postos de Gasolina

A gigante petrolífera da NLogonia PetroLog está planejando sua logística nos postos de gasolina.

Existem $n$ cidades na NLogonia, numeradas de $1$ à $n$, e $m$ estradas de mão duplas entre $x$ e $y$, com distância de $d$ quilômetros. Em $s$ das $n$ cidades, existem postos de gasolina da PetroLog.

A frota de transporte da PetroLogLog, a subsidiária de logística da PetroLog consiste em$k$ caminhões, cada caminhão $i$ podendo percorrer $c_i$ quilômetros com um tanque cheio. Por ser uma subsidiária, os caminhões da PetroLogLog podem abastecer nos postos da PetroLog de graça. Cada caminhão também tem uma rota, que inicia na cidade $a_i$ e termina boa cidade $b_i$, ambas contém um posto de gasolina.

Ajude a PetroLogLog a descobrir, para cada caminhão se é possível cumprir a rota designada, reabastecendo nos postos.

Entrada:

A primeira linha contém três inteiros $n, s, m$. A segunda linha contém $s$ números, os números das cidades que contém um posto de gasolina.

As próximas $m$ linhas contém três inteiros $x$, $y$ e $d$, que descrevem as estradas.

A próxima linha contém um inteiro $k$, o número de caminhões, seguido por $k$ linhas, cada uma com três inteiros $a_i, b_i, c_i$, a descrição de cada caminhão.

Saída:

Seu programa deve escrever $k$ linhas, onde a $i$-ésima linha deve conter $TAK$ se o $i$-ésimo caminhão ser capaz de cumprir sua rota ou $NIE$ se não for capaz.

Restrições:

• $2 \leq s \leq n \leq 2 * 10^5$
• $1 \leq m \leq 2 * 10^5$
• $1 \leq x, y \leq n$ para toda estrada
• $1 \leq d \leq 10^4$ para toda estrada
• $1 \leq k \leq 2 * 10^5$
• $1 \leq a_i, b_i \leq n$
• $1 \leq c_i \leq 2 * 10^9$

Exemplo:

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

TAK
TAK
TAK
NIE

Para submeter sua solução: SZKOPUL