输入描述:

第一行两个正整数 ，表示分别店铺个数以及询问次数。
第二行  个正整数 ，第个整数表示第  家店铺中的鱼的库存量。

后面  行，每行三个整数  , 分别代表询问的一段店铺区间以及快乐值。

输出描述:

输出  行，每行一个整数，依次表示询问对应的答案，答案对  取模。