Optimal Token Movement Game

We define the following impartial game. You are given a positive integer (m) and a sequence (b = [b_1, b_2, \dots, b_n]) of non‐negative integers. Before the game starts a chess piece is placed on the first element (position 1) of the sequence and (b_1) is decremented by 1. Then the two players, YSGH (first mover) and YGSH (second mover), take turns. In each move, suppose the chess piece is currently at position (i) (1-indexed) in the sequence. The current player must choose an index (j) with [ i \le j \le \min(i+m, n)] such that (b_j > 0). Then, the chess piece is moved to position (j) and (b_j) is decremented by 1. If at a player’s turn no valid move exists, that player loses.

It turns out that the sequence (b) used for a game is a contiguous nonempty subarray of another sequence (a = [a_1, a_2, \dots, a_n]) (both (a) and the chosen subarray are determined by YSGS). Now, there are (q) rounds. In each round you are given two integers (l) and (r) specifying that the subarray (b = [a_l, a_{l+1}, \dots, a_r]) is used for that round. Assuming both players play optimally, determine the winner of each round.

A useful way to think about the game is the following. When the chess piece is at a position (i) with current available moves counted by (c = b_i-1) (recall that initially one token is used at position 1), the player has two kinds of options:

1. If there is a valid jump (i.e. there exists some (j) with (i < j \le \min(i+m, n)) having (b_j > 0)), then the move is to jump to some such (j). Before jumping the player may choose to make some "staying moves" at the current position (i.e. moving from (i) to (i)) which each subtract one token and flip the turn. However, if (c=0) no move is possible. In particular, if a jump is available and (c \ge 1) the only option when no extra staying move is taken (i.e. with (x=0)) will switch the turn. Moreover, if (c \ge 2) the player can choose to take an odd number of staying moves (for example, (x=1)) so that the turn does not change upon jumping. It can be shown that under optimal play one may decide the outcome by a recurrence defined on the state ((i,c)) (with (c = b_i-1)).

2. If no jump is available from (i) (i.e. for every (j \in [i, \min(i+m,n)]) we have (b_j = 0)), the only option is to take the staying moves until the tokens are exhausted. In this case the outcome is determined by the parity of (c); the current player wins if (c) is odd and loses if (c) is even.

An equivalent (and rather simple) recurrence that works is as follows. Let (F(i,c)) be the outcome (winning status for the current player) when the chess piece is at position (i) with available token count (c = b_i-1). Then:

• If (c = 0) then (F(i,0)= false) (i.e. the current player loses).
• Otherwise, let (J\n = { j \mid i+1 \le j \le \min(i+m,n) ; \text{and} ; b_j > 0 }). (\bullet) If (J) is nonempty and (c = 1) then (F(i,1)= true) if there exists any (j \in J) with (F(j, b_j-1)= false); otherwise (F(i,1)= false). (\bullet) If (J) is nonempty and (c \ge 2) then (F(i,c)= true) (the current player can force a win). (\bullet) If (J) is empty then (F(i,c)= true) if (c) is odd and false otherwise.

The initial state of a game played on a subarray (b = [a_l,\dots,a_r]) is (F(1, a_l-1)) (since one token is removed from the first element before the game begins).

Your task is to answer (q) rounds. For each round, print the winner: print “YSGH” if the first player wins and “YGSH” otherwise.

inputFormat

The first line contains three integers \(m, n, q\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\). (\(0 \le a_i\); note that the subarray chosen in a round always has at least one positive number so that the game can be played.)

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-indexed) indicating that the subarray \(b = [a_l, a_{l+1}, \dots, a_r]\) is used in that round.

outputFormat

For each round, output a single line containing either YSGH if the first player (YSGH) wins or YGSH if the second player wins.

sample

1 3 3
1 1 1
1 3
1 1
2 3

YGSH
YGSH
YGSH