Artwork

Time limit1.5sMemory limit512 MB

Summary

Given up to 1000 circular sensor regions inside a rectangle, decide whether a path exists from the (0,0) corner to the opposite corner staying outside every circle.

Level: Medium7 of 10
Topics: Geometry, Union-find, Graph, Math
Solved: No attempts yet

Problem

The Mona Dura is one of the most valuable artworks in Nlogonia Museum. This famous painting is displayed in a rectangular room of M by N meters. The room's entrance is in a corner, and the Mona is in the corner diagonally opposite the entrance.

To prevent theft, the room has motion sensors that activate every night when the museum closes. Each sensor has a sensitivity S, so the sensor triggers an alarm if it detects any movement at no more than S meters from its location.

Tonight a thief broke into the museum to steal the Mona Dura. To succeed, the thief must enter the room and reach the painting without being detected by any motion sensor. That is, he must keep a distance greater than Si meters from the i-th sensor at all times, for all sensors.

The thief has access to the museum's blueprints, so he knows the size of the room and the coordinates and sensitivities of each motion sensor. Given this information, determine whether it is possible for the thief to steal the Mona Dura.

Input

The first line of input contains three integers M, N, and K, the size of the room and the number of sensors. (10 ≤ M, N ≤ 104, 1 ≤ K ≤ 1000). The room's entrance is at (0, 0), and the painting is at (M, N).

Each of the next K lines describes one of the K sensors with three integers X, Y, and S, where (X, Y) is the sensor's location and S is its sensitivity. (0 < X < M, 0 < Y < N, 0 < S ≤ 104). All dimensions and coordinates in the input are in meters. All sensors have distinct coordinates.

Output

Your program must output a single line containing the character 'S' if the painting can be stolen, or the character 'N' otherwise.

Examples3

Example 1
Input
```
10 22 2
4 6 5
6 16 5
```
Expected output
```
S
```
Example 2
Input
```
10 10 2
3 7 4
5 4 4
```
Expected output
```
N
```
Example 3
Input
```
100 100 3
40 50 30
5 90 50
90 10 5
```
Expected output
```
S
```