题目描述

瓜瓜有一个 $1 \times n$ 的条状棋盘，从左到右的位置编号是 $1, \cdots, n$。每个位置上都有一个数字 $a_i$，表示位置 $i$ 能跳到的下一个位置是 $a_i$。

瓜瓜会进行 $m$ 次游戏，每次游戏给定一个起始位置 $x$ 和允许跳跃的区间 $[l, r]$，瓜瓜只能在该区间内跳跃。瓜瓜想知道每轮游戏最多跳几次？

输入描述

第一行有两个正整数 $n, m$，其中 $1 \leqslant n, m \leqslant 2 \times 10^5$。

第二行有 $n$ 个正整数 $a_i$，其中 $1 \leqslant a_i \leqslant n$。

接下来 $m$ 行，每行有三个正整数 $l, r, x$，表示允许跳跃的区间和起始位置，其中 $1 \leqslant l, r, x \leqslant n$，保证 $l \leqslant x \leqslant r$。

输出描述

输出共 $m$ 行，每行有一个数字，表示跳跃的次数。如果能永远跳跃，则输出 $\texttt{INF}$。

样例

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

INF
0
2