问题描述

小赖给出了一个长度为 $n$ 的数组 $a$ , 包含 ${a_1, a_2, ... a_n}$，以及一个数 $q$，表示接下来有 $q$ 轮比拼。

在每一轮比拼中，小赖会给出两个正整数 $l$ 和 $r$，保证 $1 \le l < r \le n$，这两个数表示数组 $a$ 的一个区间 $[l, r]$ （包括 $a_l$ 和 $a_r$）。

小谢和小石需要在该区间内选择一个数进行比拼，谁选择的数更大谁就获胜，如果选择的数的值相同，则为平局。

然而，小谢总是能迅速找到区间[l, r]内的最大值 $a_i , i ∈ [l, r]$ 作为自己的数，而一旦小谢选了 $a_i$，小石就不能再选择 $a_i$ 了。

为了增加胜利的机会，小石插入了U盘，启动了特殊软件：现在小石可以将原区间 $[l, r]$ 变为新区间 $[L, R]$ （包括 $a_L$ 和 $a_R$），其中 $L$ , $R$ 需满足式子： $l * r = L * R$, 且新区间$[L, R]$ 依旧满足 $1 \le L < R \le n$ ; 然后，小石会选择新区间 $[L, R]$ 内的最大值作为自己的数（除了小谢选择过的数 $a_i$) 。当然了，小石会找到最好的新区间 $[L, R]$ ，使得他能选到的数值最大。

对于每轮比拼，数值更大的人为胜者，另一方为败者，如果小石获胜，请输出"S is winner d"，如果小谢获胜，请输出"X is winner d"，其中 d 表示胜者的数值减去败者的数值的值。特别的，如果两人所得数值相同，则为平局，请输出"Tie"。

输入格式

第一行两个正整数 $n$ , $q$ , 分别表示数组的长度和比拼的轮数。

第二行给出 $n$ 个数, 第 $i$ 个数代表 $a_i$。

接下来的 $q$ 行，每行给出两个正整数：$l$ , $r$ ，表示给出的区间的左右端点。

输出格式

对于给出的 $q$ 轮比拼 ，每行分别输出对应的结果：如果小石获胜，请输出"S is winner d"，如果小谢获胜，请输出"X is winner d"，其中d表示胜者的数字减去败者的数字的值。如果是平局，请输出"Tie"。

输入样例

6 3
1 3 2 3 4 5
1 4
3 4
4 5

输出样例

Tie
S is winner 2
X is winner 1

评测数据规模

对于所有评测数据： $1 \le n, a_i, q \le 10^5$ , $1 \le l < r \le n$。

说明

样例解释：

第一轮，虽然小石无法找到更好的满足条件的新区间，但是可以选择到和小谢一样的 3，此时为平局，输出 "Tie"

第二轮，小谢先选择了区间 [3, 4] 中的最大值 $a_4 = 3$ , 此时小石可以选择新区间 [2, 6] : 3 * 4 = 2 * 6 = 12 且 $1 < 2 < 6 \le 6$ , 显然该区间满足要求条件 , 然后小石选择该区间内的最大值(小谢选过的数$a_i$不可选) : $a_6 = 5$ , 此时: $5 > 3 , 5 - 3 = 2$ , 因此输出 "S is winner 2"

第三轮, 小谢先选择了区间 [4, 5] 中的最大值 $a_5 = 4$ , 此时小石没有更好的满足条件的新区间 , 最后也只能选择 $a_4 = 3$ , 此时 $4 > 3 , 4 - 3 = 1$ , 因此输出 "X is winner 1"