The setting of this problem is the same as Problem G. The differences from Problem G are underlined.

You are given a string $S$ of length $N$ consisting only of ( and ).

Answer $Q$ queries. In the $i$-th query, you are given integers $L_i$ and $R_i$. Solve the following problem:

Let $X$ be the substring of $S$ from the $L_i$-th character to the $R_i$-th character. Consider choosing a positive integer $k$ and then choosing a substring $Y$ of the string obtained by concatenating $k$ copies of $X$. Here, $Y$ must be a regular bracket sequence. $Y$ is allowed to be an empty string.

Determine whether there exists a maximum possible length for $Y$.

Regular Bracket Sequence

A regular bracket sequence is a string that can be reduced to an empty string by repeatedly removing the contiguous substring () zero or more times.

Input

The input is given from Standard Input in the following format:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$ are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ is a string of length $N$ consisting only of ( and ).
• $1 \le L_i \le R_i \le N$

Output

Print $Q$ lines. For the $i$-th line, print Finite if there exists a maximum possible length for $Y$ in the $i$-th query, and Infinite otherwise.

Example

Sample Input 1

4 3
()((
2 3
1 4
3 4

Sample Output 1

Infinite
Finite
Finite

Note

• In the first query, $X =$ )(. For any positive integer $k$, if we concatenate $k$ copies of $X$ and remove the first and last characters, we obtain a regular bracket sequence of length $2k - 2$. Therefore, there is no maximum possible length for $Y$, so you should print Infinite.
• In the second query, $X =$ ()((. It can be proven that the maximum possible length of $Y$ is $2$. Therefore, print Finite.
• In the third query, $X =$ ((. The maximum possible length of $Y$ is $0$, so print Finite. Note that $Y$ can be an empty string.