T424283 「shury OI Round I」爱情的救赎

Xwty 在前厅收到了感情创伤，他的女朋友跟他分手了。幸运的是，他发现了一个神奇的 backrooms 层级，似乎可以治愈他。那就是 level love。他将跟着实体——“ta”一起共度余生， >你是谁？为什么你跟她这么像。\ 我就是她呀，你难道不记得了吗？

你知道吗，其实在第 $18$ 分钟，ta 就会出现。你千万不要害怕，ta 对你没有敌意。 在 $5$ 小时 $21$ 分钟时，你会感觉到疲惫，但是不用担心，只要帮助 ta 一个小忙就能安稳的睡去。 ta 带你去了花店，并且给你了 $n$ 个花盆，里面插满了你们对未来的憧憬，你也许会感觉很陌生，但是不要担心，在第 $i$ 分钟时 $l_i$ 到 $r_i$ 的花盆中就会开出 $x_i$ 朵艳丽的花。你不用担心他们枯萎，他们在某种效应下，是永生的。值得注意的是，ta 给了你 $t$ 分钟去等待开花，并且一开始，花盆中会有一些花。$t$ 分钟后，ta 会问你 $m$ 个问题，每次给你一个数字 $p$，你需要找到一个**最长**子区间 $[i,j]$，使得这区间内最多的花的个数减最少的花的个数不大于 $p$。也就是说，设区间内最多的花的个数为 $mx$，最少的花的个数为 $mi$，这个区间需要满足 $mx-mi\le p$。请你帮助 ta 找出最长的连续区间。 >你说，花有重开日，我和她还有重逢的日子吗？\ 一定会的，亲爱的。

输入共 $t+m+1$ 行。 第一行共三个整数 $n,m,t$。 接下来一行，共 $n$ 个整数，$a_i$ 表示第 $i$ 个花盆中初始花的数量。 接下来 $t$ 行，每行三个整数 $l_i,r_i,x_i$。 接下来 $m$ 行，每行一个整数 $p$。 >我发现我好像在一场梦境中，但是这一切却无比的真实。亲爱的，咱们能不能在这共度余生？\ 当然，亲爱的，我永远陪着你。

输出共 $m$ 行，每行一个整数，表示最长区间内花盆的个数。 >这些日子谢谢你的陪伴，可是亲爱的，你该走出去了。

| 测试点编号： | 数据范围： | 特殊性质： | | :----------: | :----------: | :----------: | | $1-2$ | $1 \le n,l_i,r_i,x_i\le 100$，$1\le p\le10^{18}$，$1\le m,t,a_i\le 10$，$1\le l_i,r_i\le n$ | 有 | | $3-7 $ | $1 \le n,l_i,r_i,x_i\le 100$，$1\le p\le10^{18}$，$1\le m,t,a_i\le 10$，$1\le l_i,r_i\le n$ | 无 | | $8-12$ | $1 \le n,l_i,r_i,x_i\le 10^3$，$1\le p\le10^{18}$，$1\le m,t,a_i\le 10$，$1\le l_i,r_i\le n$ | 无 | | $13-20$ | $1 \le n,l_i,r_i,x_i\le 10^5$，$1\le p\le10^{18}$，$1\le m,t,a_i\le 100$，$1\le l_i,r_i\le n$ | 无| 对于 $100\%$ 的数据，$1 \le n,l_i,r_i,x_i\le 10^5$，$1\le p\le10^{18}$，$1\le m,t,a_i\le 100$，$1\le l_i,r_i\le n$。 特殊性质：保证每次询问的 $p$ 都大于所有花盆中花的个数。 >听着，亲爱的。这里的一切不真实，简单来说，这是一场梦境。我知道，你在前厅受到了感情创伤。但是我要告诉你的是，幻想终究不是现实，用梦来麻痹自己，并不是勇敢的行为。你要走出来。带着我送你的戒指，穿过这道门吧。再见，亲爱的，感谢你 $520$ 天的陪伴！