题目描述

婚后生活的一大挑战是决定家务由谁来做。一对新婚夫妇决定通过游戏来解决这些问题。

所有游戏都在同一棵带权树上进行。树有 $N$ 个顶点，编号为 $0$ 到 $N-1$，以 $0$ 为根。对每个 $i>0$，记 parent[i] 为它的父亲，weight[i] 为边 $(i,parent[i])$ 的权值。

树由下面的伪随机过程生成。初始随机状态为输入中的 state：

def rnd():
    state = (state * 1103515245 + 12345) modulo 2^31
    return state

for i = 1 to N-1:
    parent[i] = max(0, i - 1 - (rnd() % D))

bank = empty sequence
for i = 0 to B-1:
    bank.append(rnd() % N)

for i = 1 to N-1:
    if rnd() % 100 < P:
        weight[i] = rnd() % N
    else:
        weight[i] = bank[rnd() % B]

请严格按照上述顺序生成数据：先生成全部 parent，再生成 bank，最后生成全部边权。

一次游戏由四个参数 $(U,V,hi,lo)$ 决定，游戏只在树上从 $U$ 到 $V$ 的简单路径上进行。路径上的每条边起初都没有棋子。新娘先手，两人轮流操作。

游戏中维护一个变量 $X$，初始 $X=hi$。每次操作时，当前玩家必须选择路径上一条尚未放置棋子且权值不超过 $X$ 的边，在其上放置棋子，然后令 $X$ 等于该边的权值。无法进行合法操作的玩家失败。此外，如果某位玩家被迫选择权值小于 $lo$ 的边，也立即失败。

接下来还要用同一个伪随机状态（即生成完树和边权后的 state）依次生成 $Q$ 个询问：

for q = 0 to Q-1:
    U  = rnd() % N
    V  = rnd() % N
    hi = rnd() % N

对于每个询问 $(U,V,hi)$，考虑所有 $lo\in[0,hi]$。设 answer[q] 为其中使得双方都采取最优策略时新郎获胜的 $lo$ 的数量。

求所有询问的 answer[q] 之和。

输入格式

一行六个整数：

N D state B P Q

含义与题目描述相同。

输出格式

输出一个整数，表示全部 $Q$ 个询问答案之和。

数据范围

• $2\le N\le 100000$；
• $1\le D\le N$；
• $0\le state<2^{31}$；
• $1\le B\le N$；
• $0\le P\le100$；
• $1\le Q\le200000$。

样例 1

7 2 47474747 2 50 9

10

样例 2

7 2 47474747 1 0 9

23