H. Sequential Nim
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Susu discovered a game that involved $$$N$$$ piles of stones where the $$$k^{\text{th}}$$$ pile has $$$s_k$$$ stones. The game is played between two players. The players take turns removing stones from the piles with the following rules:

  • A player can remove any positive number of stones from a single pile in turn.
  • A player cannot remove stones from a pile until all the stones in the piles with lower indices have been removed.
  • The player who cannot make a valid move loses.
There are two types of queries you need to handle:

Type 1: Update the size of the $$$i^{\text{th}}$$$ pile to $$$x$$$.

Type 2: Given a range of piles L to R, determine which player will win the game if they play optimally.

As you are a skilled programmer, you decide to implement this game. Can you write a program to solve this game?

Input

The first line of input contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \le N, Q \le 10^5)$$$ — the number of piles and the number of queries, respectively.

The second line of input contains $$$N$$$ integers $$$s_1, s_2, ..., s_N (1 \le s_i \le 10^9)$$$ — the initial sizes of the piles.

Each of the following $$$Q$$$ lines contains a query in the following format:

  • 1 $$$i \; x$$$: update the $$$i^{\text{th}}$$$ pile to size $$$x (1 \le i \le N, 1 \le x \le 10^9)$$$.
  • 2 $$$L \; R$$$: which player will win the game if they play optimally using only the piles from L to R $$$(1 \le L \le R \le N)$$$.
Output

For each query of type 2, output a single line containing either "First" or "Second", depending on which player will win the game if they play optimally.

Example
Input
5 3
20 1 1 2 5
2 1 3
1 5 3
2 3 5
Output
First
Second