给出长度为n的序列，序列中有个元素，你需要进行次查询，每次查询形如以下格式： ：你需要选择两个整数满足，使得最大化。

输入描述:

第一行两个整数第二行n个整数接下来行每行三个整数表示一个查询

输出描述:

对于每个查询输出一个整数表示的最大值。