問題文

taiga 君は次のような問題を作りました。

Simple Nim

整数列 $(C_1,C_2,\dots ,C_k)$ を用いて F 君と S 君は石取りゲームを行います。 最初 $k$ 個の石の山が左右一列に並んでおり、左から $i$ 番目の石の山には $C_i$ 個の石があります。 F 君から始めて $2$ 人は交互に以下の操作を繰り返します。

• 石が $1$ 個以上残っている山のうち最も右にあるものを選ぶ。 その山に $n$ 個の石があるとき、$1$ 個以上 $n$ 個以下の任意の個数の石をその山から取り除く。

先に操作できなくなったプレイヤーが負けとなります。どちらが勝ちますか？

長さ $N$ の整数列 $A$ と $Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは三つの整数 $T_i,X_i,Y_i$ が与えられるので以下の処理を行ってください。

• $T_i=1$ のとき、$A_{X_i}$ を $Y_i$ で置き換える。

• $T_i=2$ のとき、$C=(A_{X_i},A_{X_i+1},\dots,A_{Y_i})$ とした時の問題 "Simple Nim" の答えを出力する。

入力

$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$

出力

$T_i=2$ であるような各クエリについて、"Simple Nim" で F 君が勝つなら F と、 S 君が勝つなら S と出力してください。

サンプル

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