给定长度为的初始序列，接下来有次操作： 对于操作1,输入表示对区间加一个首项为,公差为的等差数列。 对于操作2,输入,表示询问区间的和,并且对取模。

输入描述:

第一行输入整数。接下来输入个整数。接下来输入一个正整数。接下来行,每一行首先输入一个整数：当时,接下来输入表示第一种操作。当时,接下来输入, 且为素数，表示第二种操作。

输出描述:

对于每个操作2,输出询问的答案。