Dexter lives with his girlfriend, Hannah. He plans to spend today's evening with her, driving his new car. The cities in his state are connected to each other via bi-directional roads in such a way that they form a tree.

As he has many enemies in the city, he needs to be careful in choosing the path for the road trip. In each city, resides a member of a certain gang, which wants to kill Dexter. Whenever Dexter passes through that city, the members of that gang become alert. Now, the good thing about these gangs for Dexter is that these gangs hate each other and don't go well with each other. So, a path is dangerous for dexter if and only if a gang exists on that path in majority. Otherwise the gang members end up fighting each other and the path becomes clear for dexter.

Definition of majority on a path : If the number of cities occupied by gang members of gang G on a path are x and the number of cities on that path are n, then gang G is in majority on that path if and only if \(x > n/2\) .

There are N cities in the state and there are \(N-1\) bi-directional roads. Hannah comes up with M plans for the road trip. Each plan is of the form \(u , v\), where road trip will take place from the city u to the city v along the unique path between them. For each plan, you need to tell whether the path in that plan is dangerous or not, and if it is dangerous, you need to output the number of the gang which is in majority on that path.

Input

First line of input contains two integers N and M, where N is the number of cities in the state and M is the number of plans suggested by Hannah. Next line contains N space separated integers G_i, where G_i is the number of the gang of the gang member in city i. Each of the next \(N-1\) lines contain two integers u and v, where u and v have a bi-directional road between them. Next M lines describe the query, i.e., the plan suggested by Hannah. Each of these lines contain two integers p and q, which represents the path between p and q.

Output

You need to output M lines. i^\(th\) query is answered by i^\(th\) line. If the path in the i^\(th\) query is safe for Dexter, outpur "S" (withour quotes). If that path is dangerous and gang numbered x is in majority on that path, output "D x" (without quotes).

Constraints

\(1 ≤ N ≤ 10\)⁵
\(1 ≤ M ≤ 10\)⁶
\(1 ≤ G\)_i \(≤ 10\)⁹
\(1 ≤u , v ≤ N\)
\(1 ≤ p , q ≤ N\)

For \(30 \%\) score : \(1 ≤ N , M ≤ 10\)³
For Full score : Original Constraints