#300. [ONTAK2010]Peaks加强版

[ONTAK2010]Peaks加强版

[ONTAK2010] Peaks 加强版

题目背景

原题链接:P4197 Peaks

题目描述

给定一张 nn 个点、mm 条边的无向图,第 ii 个点的权值为 aia_i,边有边权。

qq 组询问,每组询问给定三个整数 u,x,ku, x, k,求从 uu 开始只经过权值 x\leq x 的边所能到达的权值第 kk 大的点的权值,如果不存在输出 1-1

本题强制在线。即:每次查询输入的是 u,x,ku', x', k',则 $u = (u' \operatorname{xor} \text{lastans}) \bmod n + 1$,kk 的解密方式与之相同,x=xxorlastansx = x' \operatorname{xor} \text{lastans}

输入格式

第一行,三个整数 n,m,qn, m, q

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

接下来 mm 行,每行三个整数 s,t,ws, t, w,表示一条边的两个端点和权值;

接下来 qq 行,每行三个整数 u,x,ku', x', k'

注意:处理第一组数据和无解时的 lastans=0\text{lastans} = 0

输出格式

对于每组询问,输出一行,一个整数,表示所求的值。

样例 #1

样例输入 #1

10 11 3
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
0 5 5
1 6 8
7 8 1

样例输出 #1

1
-1
8

提示

对于 100%100\% 的数据,1n1051 \leq n \leq 10^50m,q5×1050 \leq m, q \leq 5 \times 10^51s,tn1 \leq s, t \leq n1ai,w1091 \leq a_i, w \leq 10^90u,x,k<2310 \leq u', x', k' < 2^{31}