将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

1. 询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。

2. 修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

给出一个 $n$ 个节点的有根树。有 $q$ 次询问，每次询问给出 $l,r,z$ ，求 $\sum _ {l \leq i \leq r}dep[LCA(i,z)]$ 。

超级计算机中的任务用三元组 $(S_i,E_i,P_i)$ 描述， $(S_i,E_i,P_i)$ 表示任务运行区间为 $[S_i,E_i]$ ,其优先级为 $P_i$ 。

给出 $n$ 个任务。随后给出 $m$ 个询问，第 $X_i$ 秒正在运行的任务中，优先级最小的 $K_i$ 个任务的优先级之和是多少。特别的，如果 $K_i$ 大于第 $X_i$ 秒正在运行的任务总数，则直接回答第 $X_i$ 秒正在运行的任务优先级之和。

强制在线。