或真亦或伪？飘如陌上尘。
对于长度为 的序列 ，有以下三种操作：
需要通过若干次操作将 的每个元素变为同一个非负整数 ，设消耗的总代价为 。记 为所有可行方案中 的最小值。
有一个长为 的序列 ，有 次操作，每次为其中之一：
第一行输入两个数 。
第二行输入 个数，第 个数表示 。
接下来 行，第一个数为 表示操作类型，若 ，接下来输入三个数 ，表示一次修改；否则输入两个数 ，表示一次询问。
输出若干行，对应每次询问的答案，对 取模。
3 6 1 2 3 2 1 2 1 3 3 2 2 2 3 2 1 3 1 1 2 4 2 1 3
1000000005 1000000002 2 5
本题 I/O 量较大，请使用较快的 I/O 方式。
对于第一个询问，序列 可以为 ， 分别为 ，和为 ，在模 意义下为 。
对于 的数据，保证： ，，，，。
特殊性质 A：数据中任意时刻 单调不降。
特殊性质 B：数据中不包含修改操作。
