Phebe and Ryan
Description
| Phebe found herself facing a difficult situation, hurt and betrayed by Ryan's actions. Ryan, aware of the gravity of his mistake, understood the immense challenge he faced in trying to salvage their relationship. Taking a deep breath, he approached Phebe, hoping to find the right words to convince her not to end things. "Phebe, I understand that I have hurt you deeply, and I'm truly sorry for my actions. I know I can't change the past, but please give me a chance to explain and work things out together." Phebe looked at Ryan with a mix of anger and sadness, unsure if she could trust him again. Ryan continued, his voice filled with sincerity and remorse. "Phebe, please write a computer program to solve the following problem." |
Among Phebe and Ryan is a pile of blocks, each weighing some integer number of kilograms. There is also a scale, initially reading zero kilograms. Phebe and Ryan take turns picking any block, and placing it on top of the scale (after which the reading on the scale increases by the weight of the block). The first player who either makes the scale read exactly $k$, or runs out of blocks to place, loses. Phebe makes the first move.
You are given an array of $n$ integers $a_1, a_2, ..., a_n$. Please process $q$ of the following two types of queries:
- SET $i, x$: Set $a_i$ to $x$.
- ? $k$: Phebe and Ryan play the aforementioned game using $\sum a_i$ blocks. For all $1 \leq i \leq n$, there are $a_i$ blocks weighing $i$ kilograms. If the game uses the given parameter $k$, and both players play optimally, who will win?
The first line of input consists of two space-separated integers $n$ and $q$ $(1 \leq n, q \leq 2 \cdot 10^5)$.
The second line consists of $n$ space-separated integers $a_1, a_2, ..., a_n$ $(0 \leq a_i \leq 10^8)$.
The next $q$ lines each consist of a query, which is described by one of the following:
- The string SET followed by a space, followed by two space-separated integers $i$ and $x$ $(1 \leq i \leq n$, $0 \leq x \leq 10^8)$.
- The string ? followed by a space, followed by a single integer $k$ $(1 \leq k \leq 10^{18})$.
It is guaranteed that during any ? query, $\sum a_i > 0$.
If there are $k$ ? queries, output $k$ lines.
On the $i$th line, if Phebe will win the game under the conditions of the $i$th ? query, output the string PHEBE, otherwise output the string RYAN.
Input
The first line of input consists of two space-separated integers $n$ and $q$ $(1 \leq n, q \leq 2 \cdot 10^5)$.
The second line consists of $n$ space-separated integers $a_1, a_2, ..., a_n$ $(0 \leq a_i \leq 10^8)$.
The next $q$ lines each consist of a query, which is described by one of the following:
- The string SET followed by a space, followed by two space-separated integers $i$ and $x$ $(1 \leq i \leq n$, $0 \leq x \leq 10^8)$.
- The string ? followed by a space, followed by a single integer $k$ $(1 \leq k \leq 10^{18})$.
It is guaranteed that during any ? query, $\sum a_i > 0$.
Output
If there are $k$ ? queries, output $k$ lines.
On the $i$th line, if Phebe will win the game under the conditions of the $i$th ? query, output the string PHEBE, otherwise output the string RYAN.
5 6
0 2 3 0 0
? 10
SET 5 1
? 10
SET 1 50
? 37
? 38
6 10
1 1 1 1 1 1
? 21
? 31
SET 6 0
? 5
SET 2 5
? 17
? 20
SET 3 10
? 10
? 1000000000000000000
PHEBE
RYAN
RYAN
PHEBE
PHEBE
RYAN
PHEBE
PHEBE
PHEBE
RYAN
RYAN
Note
In the first query of the first sample test case, Phebe and Ryan play the game using $2$ blocks of weight $2$ and $3$ blocks of weight $3$. One possible game with both players playing optimally is the following:
- Phebe picks a block of weight $2$. The scale now reads $2$.
- Ryan picks a block of weight $3$. The scale now reads $5$.
- Phebe picks a block of weight $2$. The scale now reads $7$.
- Ryan is forced to pick a block of weight $3$. The scale now reads $10$ and Phebe wins.