問題一覧 > 通常問題

No.1801 Segment Game

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 110
作問者 : NatsubiSogan / テスター : first_vil penguinman
お気に入りにしたユーザー ProblemId : 7064 / 自分の提出
問題文最終更新日: 2021-12-20 01:15:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 326 (順位表) の他の問題:

Problem Statement

On a two-dimensional plane, there is a rectangle with the $4$ points $(0,0), \ (0,H), \ (W,0), \ (W,H)$ as its vertices.

Natsubi and Sogan play a game using this rectangle. Starting with Natsubi, they alternately perform the following operation.

  • Choose points $(x_1,y_1), \ (x_2,y_2)$ whose distance is at most $D$ and which are distinct on the perimeter lattice points (points whose $x$ and $y$ coordinates are both integers) of the rectangle, and draw the segment connecting $(x_1,y_1)$ and $(x_2,y_2)$ on the plane.
  • However, the segment must not share any point with any of the already drawn segments inside the rectangle (including its perimeter).

The player who first becomes unable to perform the operation loses. When both players play optimally, which of them wins?

You are given $T$ test cases; find the answer for each of them.

Input

On line $1$ of the input, the number of test cases $T$ is given in the following format.

$T$

Then, $T$ test cases follow. Each of them is given in the following format.

$H$ $W$ $D$
  • All input values are integers.
  • $1 \leq T \leq 10^5$
  • $1 \leq H,W,D \leq 10^9$

Output

Print $T$ lines.

On line $i \ (1 \leq i \leq T)$, print N if Natsubi wins the $i$-th test case, and S if Sogan wins it.

Print a newline at the end.

Sample

Sample 1
Input
5
1 1 2
1 1 1
31 41 59
26 53 58
97 93 23
Output
N
S
N
N
S
  • Case $1$: If Natsubi draws the segment connecting $(0,0),\ (1,1)$, Sogan has no segment left to draw. Therefore, Natsubi has a winning strategy.
  • Case $2$: The segment connecting $(0,0),\ (1,1)$ has length $\sqrt{2} \ (>1)$, so it cannot be chosen. For example, if Natsubi draws the segment connecting $(0,0),\ (0,1)$, Sogan has no choice but to draw the segment connecting $(1,0),\ (1,1)$. Then, Natsubi has no segment left to draw. Therefore, Sogan wins.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。