玄学
时间限制：80s 空间限制：768MB
题目描述
巨酱有n副耳机，他把它们摆成了一列，并且由1到n依次编号。每个耳机有一个玄学值，反映了各自的一些不可名状的独特性能。玄学值都是0到m−1间的整数。在外界的作用下（包括但不限于换线、上放、更换电源为核电、让kAc叔叔给它们讲故事），这些耳机的玄学值会发生改变。特别地，巨酱观察发现，每种作用o对应了两个整数ao与bo，在这种作用之后，玄学值原本为x的耳机，其玄学值恰会变成(ao*x+bo)modm。
巨酱对他手头耳机的表现并不满意，遗憾的是，最近他并不有钱，无法任性，不能赶紧买买买以满足自己。手头紧张的他准备拟定一个相对经济的方案，通过各种作用来改善他手头玩具的性能。具体地说，为了尽快完成方案的制订，巨酱希望自己能高效地完成以下工作：
巨酱想到了一种操作，能让耳机的玄学值由x变为(ax+b)modm，并且他计划对编号为i到j的耳机执行这种操作。
巨酱想知道如果将（并且仅将）自己的第i个到第j个计划按顺序付诸行动，编号为k的耳机的玄学值将会变成多少。
出于著名算法竞赛选手的矜持，巨酱表示自己才不需要你的帮助。但是如果巨酱真的厌倦了自己的玩具，它们就会被50包邮出给主席。为了不让后者白白捡到便宜，你考虑再三还是决定出手。
输入格式
第1行只有一个整数，表示本组测试数据的特征。特征值为一个0∼31的整数。我们把这个整数转换成一个五位的二进制数，最低位为第一位。
如果第一位为1，代表数据进行了加密，否则数据没有进行加密。对于已加密的数据，你需要把第一种操作中的i,j以及第二种操作中的i,j,k与上一次询问操作得到的答案lastans进行异或操作来得到正确的操作信息。lastans的初始值视为0。
如果第二位为1，代表修改操作会出现(0*x+b)mod m（b不为0）的形式，否则一定不会出现这样的修改。
如果第三位为1，代表修改操作会出现(a*x+0)mod m（a不为0）的形式，否则一定不会出现这样的修改。
如果第四位为1，代表修改操作会出现(a*x+b)mod m（a,b均不为0）的形式，否则一定不会出现这样的修改。
如果第五位为1，则我们保证给出的m是一个质数，否则不保证。
第2行两个整数n,m。
第3行有n个用空格隔开的整数a1,a2,…,an，0≤ai<m，表示第i副耳机原本的玄学值。
第4行一个整数q，表示巨酱的操作总数。
输出格式
对每个第2类操作，输出独占一行的一个整数，表示那次询问的结果。
样例输入
24 35 123 5 11232 12343 2113 11314 2132
样例输出
3 4 其中 x 为 0 和 1 中的任意数，特征值最左边为最高位。我们保证，同类型的测试点中加密与不加密的数据点各占 50%，且修改操作数不超过 100000，所有数的都可以用 int 存下。 由于本题数据量较大，请自行使用读入优化；由于测试点较多以及时限较长，为了大家的正常做题，请尽量减少提交本题的次数。 N<=100000 q<="600000" 特征值xxxxx<="" pre="">提示
没有写明提示
题目来源
2015年国家集训队测试