题目背景

2025 年的最后一天，拾柒在街角摆了一排烟花，准备迎接 2026 年的元旦。

为了“年味儿”，拾柒给每串烟花贴了一个编号 $a_i$。但这些编号并不是普通的数字：它们会经历一种奇怪的“压岁合并仪式”。更怪的是，店家扎绳成“束”的方式也依赖这套仪式。

“新的一年，要学会把复杂的东西压缩成简单的样子。”拾柒一边贴封条一边念叨。

于是它设计了如下规则，并抛给你一堆封条与询问，让你找出最早能把“年味预算”压到合格线的时刻。

题目描述

设常数 $B=2026$。

对任意非负整数 $x$，进行如下仪式：

• 初始时，你有 $x$ 个“0 级火星”。
• 允许重复执行操作：选择某个等级 $t\ge 0$，若当前存在 恰好 $B$ 个 $t$ 级火星，则把这 $B$ 个 $t$ 级火星合并为 1 个 $(t+1)$ 级火星。
• 当无法继续合并时停止。

将停止时各等级火星的个数记为一个序列（按等级从小到大排列），称为 $x$ 的纹样，记作 $\operatorname{Pat}(x)$。

题目保证：无论合并操作执行顺序如何，最终得到的 $\operatorname{Pat}(x)$ 都相同（即纹样是良定义的）。

定义：

称两个数 $x,y$ 相印 当且仅当 $\operatorname{Pat}(x)=\operatorname{Pat}(y)$。

给定序列 $a_1,\dots,a_n$，如果相邻两项 $a_i,a_{i+1}$ 相印，则它们会被自动扎在同一束中。 一束定义为按此规则得到的一个极大连续区间（不能再向左右扩展）。

你有 $m$ 张封条，第 $j$ 张覆盖区间 $[L_j,R_j]$，按顺序执行。

执行第 $j$ 张封条时：

• 对当前所有束中，满足“该束区间 $[l,r]$ 完全落在封条内”，即 $L_j\le l$ 且 $r\le R_j$ 的束：

  • 将这整束内所有位置的值 $a_k$ 统一替换为 $g(a_k)$。

• 执行完替换后，按“相印”规则重新自动扎绳成束（可能发生合并）。

记执行前 $t$ 张封条后的序列为 $a^{(t)}$（$t=0$ 表示不执行任何封条）。

4) 询问：最早满足预算

共有 $q$ 个询问，第 $i$ 个询问给出 $(l_i,r_i,S_i)$。你需要输出最小的 $t\in[0,m]$ 使得

若不存在这样的 $t$，输出 $-1$。

输入格式

第一行三个整数 $n,m,q$。

第二行 $n$ 个整数 $a_1,\dots,a_n$。

接下来 $m$ 行，每行两个整数 $L_j,R_j$。

接下来 $q$ 行，每行三个整数 $l_i,r_i,S_i$。

输出格式

输出共 $q$ 行，每行一个整数，表示对应询问的答案；若不存在则输出 $-1$。

6 3 4
2026 2026 5 4052 4052 2027
1 5
2 6
3 4
1 6 10000
1 5 20
3 6 10
4 6 6

1
1
-1
2

数据范围

对于 $10\%$ 的测试数据，$n,m,q\le 3000$。

对于另 $20\%$ 的测试数据，$n,m,q\le 10^5$，且每次封条区间 $[L_j,R_j]$ 都恰好对齐束边界（不会切开任何束）。

对于 $100\%$ 的测试数据：

• $1\le n,m,q\le 10^5$
• $0\le a_i\le 10^{18}$
• $1\le L_j\le R_j\le n$
• $1\le l_i\le r_i\le n$
• $0\le S_i\le 10^{18}$