#P17739. Game

Game

题目描述

给出一个由小写英文字母构成的字符串 SS,再取 nn 个字符串,它们都是 SS 的子串,之后开始游戏,两人轮流操作:

每次选一个串,在其后添加一个英文字母,保证添加后该串仍为 SS 的子串。

谁不能操作谁输,或者谁不能操作谁胜。

但是春希看出了胜负已定,于是对实际操作没有兴趣,所以 Pickupwin 只要求他指明先手是否必胜就好。

输入格式

从标准输入读入。

第一行一个字符串 SS;

第二行一个正整数 nn;

接下来 nn 行,每行两个正整数 l,rl,r,表示第 ii 个字符串由 SS 中第 ll 个至第 rr 个字符一次拼接而成( SS 中字符从 11 开始标号)

输出格式

输出到标准输出。

输出 n+nn+n 行第 2∗i−12*i-1 行输出在仅有前 ii 个子串时,谁不能操作谁输,先手是否必胜。

第 2∗i2*i 行输出在仅有前 ii 个子串时,谁不能操作谁胜,先手是否必胜。

用 Fir 表示先手必胜, Sec 表示后手必胜。

样例

输入

sroababorz
3
4 5
7 8
1 3

输出

Fir
Sec
Fir
Sec
Sec
Fir

数据范围

50% ∣S∣≤200|S|\leq 200, n≤100n\leq 100

100% ∣S∣≤106|S|\leq 10^6, n≤5∗105n\leq 5\ast 10^5