环鸽的数列
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一天 给环鸽出了一道题。环鸽看题罢，嘿嘿一笑道：“这题简单，我见过”。一天过去了， 问环鸽有没有把题切了。环鸽：滑稽挠头.gif......

现在环鸽悄悄找到你来寻求帮助。你能不能帮帮环鸽呢？
环鸽给了你一个长为 的数列 a_i，以及一个递推数列 F_i。其中 ; ; 。即它的前几项是： 。给了你下面两种操作：

1. 给你一次操作 "" ，表示对于所有 的 ，a_i 加上 。
2. 给你一次询问 "" ，表示对 的 a_i 求和，答案对 取模。

输入描述:

第一行两个整数  和  。

第二行  个整数  。

后面  行没行三个整数  ，表示一次询问。

输出描述:

对于每个询问输出一行整数，表示其答案。
示例1

输入

复制 
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

输出

复制 
64
25

说明

初始序列为 \ [1,2,3,4]。

第一次操作后为 \ [2,5,14,43] ，第一次询问 \ 2+5+14+43=64。

第二次操作后为 \ [2,6,17,54] ，第二次询问 \ 2+6+17=25。