#PU1406. USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure
USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure
USACO 2024 February Contest, Platinum — Problem 3. Infinite Adventure
题目描述
Note: The memory limit for this problem is 512MB, twice the default. Bessie is planning an infinite adventure in a land with () cities. In each city , there is a portal, as well as a cycling time . All 's are powers of , and . If you enter city 's portal on day , then you instantly exit the portal in city . Bessie has () plans for her trip, each of which consists of a tuple . In each plan, she will start in city on day . She will then do the following times: She will follow the portal in her current city, then wait one day. For each of her plans, she wants to know what city she will end up in.
输入格式
The first line contains two space-separated integers: , the number of nodes, and , the number of queries. The second line contains space-separated integers: (, is a power of , and ). For , line contains space-separated positive integers, namely (). For , line contains three space-separated positive integers, (, , and ) representing the th query.
输出格式
Print lines. The th line must contain the answer to the th query.
数据范围
(见题面原文)
样例
样例 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
Bessie's first three adventures proceed as follows:
In the first adventure, she goes from city $2$ at time $4$ to city $3$ at time $5$, to city $4$ at time $6$, to city $2$ at time $7$.
In the second adventure, she goes from city $3$ at time $3$ to city $4$ at time $4$, to city $2$ at time $5$, to city $4 $ at time $6$, to city $2$ at time $7$, to city $4$ at time $8$, to city $2$ at time $9$.
In the third adventure, she goes from city $5$ at time $3$ to city $5$ at time $4$, to city $5$ at time $5$.
样例 2
5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000
2
3
5
4
2