测试数据来自 system/1396

背景

HYH同学非常反感时间效率优秀的平衡树，于是发明了支持立方复杂度插入操作和四次方复杂度删除操作而且不支持查询操作的HYH树，HYH希望你能帮忙完善……

描述

我们假定HYH查找树是（以下简称HST，HYH's Search Tree）一颗最多有n个节点的有根树。

HYH希望你能为HST设计一个程序，能够快速地得到某两个给定节点的关系。具体地说，希望你能返回某个节点是否为另外一个节点的祖先。

HST的描述方式比较奇怪：节点按层次从1编号到n，编号为1的节点总是HST的根。每个节点的儿子个数以一个函数s(x) = ( s5 * x ^ 4 + s4 * x ^ 3 + s3 * x ^ 2 + s2 * x ^ 1 + s1 ) mod p给出（后面若干个节点可选择的节点个数（即编号已经大于n）不足s(x)个，则它的
儿子数为剩下的节点个数）。

举例来说，一颗5个节点的HST的s[1..5]=(1,2,3,4,5)，则HST的形态如图。

特别地，如果某时无法继续扩展，则剩下的节点作废，比如说1号节点有0个儿子，那么整棵树只有一个节点。

HYH同学希望你回答Q个询问，第i个询问以数对( x , y ) = ( ( a3 * i ^ 2 + a2 * i ^ 1 + a3 ) mod n + 1 , ( b3 * i ^ 2 + b2 * i ^ 1 + b3 ) mod n+1 )的形式给出，表示询问编号为x的节点是否编号为y的节点的祖先。

格式

输入格式

第一行，两个整数n和q。（n≤10^6，q≤10^3）
第二行，6个整数，表示s5、s4、s3、s2、s1和p。

第三行，6个整数，表示a3、a2、a1、b3、b2和b1。

输出格式

输出一个整数，表示一共有多少对询问(x,y)使节点x是节点y的祖先。

样例1

样例输入1

5 1
0 0 0 1 0 10000
0 0 1 0 0 4

样例输出1

1

限制

每个测试点1秒.