Problem Statement

Taiga created the following problem.

Simple Nim

F and S play a stone-taking game using an integer sequence $(C_1,C_2,\dots ,C_k)$. Initially, $k$ piles of stones are arranged in a row from left to right, and the $i$-th pile from the left contains $C_i$ stones. Starting with F, the $2$ players alternately repeat the following operation.

• Choose the rightmost pile among the piles with $1$ or more stones remaining. If that pile has $n$ stones, remove any number of stones between $1$ and $n$, inclusive, from that pile.

The player who first becomes unable to perform an operation loses. Which player wins?

You are given an integer sequence $A$ of length $N$ and $Q$ queries. In the $i$-th query, three integers $T_i,X_i,Y_i$ are given. Process it as follows.

• If $T_i=1$, replace $A_{X_i}$ with $Y_i$.

• If $T_i=2$, output the answer to the problem "Simple Nim" with $C=(A_{X_i},A_{X_i+1},\dots,A_{Y_i})$.

Input

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$\vdots$
$T_Q$ $X_Q$ $Y_Q$

Output

For each query with $T_i=2$, output F if F wins "Simple Nim", and S if S wins.

Sample

2 1
2 1
2 1 2

S

2 1
1 2
2 1 2

F

3 3
3 1 4
2 1 2
1 2 2
2 1 3

S
F