#P1533. 可怜的狗狗

可怜的狗狗

题目描述

小卡家有 nn 只狗,由于品种、年龄不同,每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比(漂亮值越低越漂亮),吃饭时,狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒,他才不肯喂这么多狗呢,这多浪费时间啊,于是他每次就只给第 ii 只到第 jj 只狗中第 kk 漂亮的狗狗喂食(好狠心的人啊)。而且为了保证某一只狗狗不会被喂太多次,他喂的每个区间 [i,j][i,j] 不互相包含。

输入格式

第一行输入两个数 n,mn,mmm 表示嘉嘉喂食的次数

第二行 nn 个整数,表示第 ii 只狗的漂亮值为 aia_i

接下来 mm 行,每行 33 个整数 i,j,ki,j,k,表示询问这次喂食喂第 ii 到第 jj 只狗中第 kk 漂亮的狗的漂亮值。

输出格式

mm 行,每行一个整数,表示每一次喂的那只狗漂亮值为多少。

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

提示

1n3×105,1m5×1041\le n \le 3\times 10^5 ,1\le m \le5\times10^4