beecrowd | 2809
# K-th Path

**Timelimit: 1**

By Gabriel Duarte, UFF Brazil

Dabriel has just learned about shortest paths in graphs and is already considered very good at it. It can always find the best route between a pair of vertices.

After spending hours playing with his graphs and finding shortest paths he thought of something interesting: Is there any other path in the graph that uses at least **K** different edges of the path he had found and that the difference of the values of these paths is at most **D**?

As Dabriel walks around without time, he asked for your help to solve this problem. It will be given a graph and a set of edges that form a shortest path, in addition an integer **Q** will be given that will represent how many queries it wishes to make.

The first line of the input contains three integers **N**, **M**, **Q** (1 ≤ **N** ≤ 10^{4}, 1 ≤ **M** ≤ min(20000, **N***(**N**-1) / 2), 1 ≤ **Q** ≤ 100), representing the quantity of vertices, the number of edges and how many queries will be made, respectively. The next line contains two integers **U** and **V** (1 ≤** U**, **V** ≤ **N**, **U **!= **V**), which represents the exit and destination vertex of the shortest path. The next line will have a list of integers **X _{i}** (1 ≤

For each query print "SIM" if there is another path with at least K different edges and with a value difference of at most D, otherwise print "NAO". The quotation marks should not be printed.

Input Sample | Output Sample |

4 6 3 |
SIM |