**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**
Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\))
городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\).
являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте
в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе
\(c_{i, t\bmod{T_i}}\).
У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия,
каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане
она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\)
раз. Она входит в портал текущего города, затем ждёт один день. Для каждого
из её планов она хочет узнать, в каком городе она закончит путешествие.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два разделённых одиночным пробелом целых числа:
\(N\), количество городов и
\(Q\), количество запросов.
Вторая строка содержит \(N\) разделённых одиночными пробелами
целых чисел: \(T_1, T_2, \ldots, T_N\) (\(1\leq T_i\), \(T_i\) степень \(2\),
и \(T_1 + \cdots + T_N \leq 10^5\)).
Для \(i = 1, 2, \ldots, N\), строка \(i+2\) содержит \(T_i\) разделённых
одиночными пробелами положительных целых чисел, а именно
\(c_{i, 0}, \ldots, c_{i, T_i-1}\) (\(1\leq c_{i, t} \leq N\)).
Для \(j = 1, 2, \ldots, Q\), строка \(j+N+2\) содержит три разделённых
одиночными пробелами положительных целых числа, \(v_j, t_j, \Delta_j\)
(\(1\leq v_j \leq N\), \(1\leq t_j \leq 10^{18}\), \(1\leq \Delta_j \leq 10^{18}\))
представляющих \(j\)-ый запрос.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(Q\) строк. \(j\)-ая строка должна содержать ответ на \(j\)-ый запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 3 6
5 3 2
5 3 7
|
2
2
5
4
|