多项式的多点求值（multi-point evaluation）是给出一个多项式 
，和 
个点 
，要求求出 
相反的，多项式的插值（interpolation）是给出 
个点 
，求出一个 次多项式，使得这些点都在这个多项式上
这两个问题实际上是在多项式的点值表示（point-value representation）和系数表示（coefficient representation）之间转换的方法，在快速傅里叶变换中由于带入值的特殊性质，可以在 
的之间内将两种东西互相转换，但是，如果是任意给定点要求求值或者插值，就没有比较好的性质可以利用，但是仍然有比较快速的方法来计算它们
强强和萌萌是一对好朋友。有一天他们在外面闲逛，突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了，无数的花瓣以肉眼可见的速度从紫荆树上长了出来。
仔细看看的话，这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点，每个节点上有一个可爱的小精灵，新长出的节点上也会同时出现一个新的小精灵。小精灵是很萌但是也很脆弱的生物，每个小精灵 
都有一个感受能力值 
，小精灵 
成为朋友当且仅当在树上 和 
的距离 
，其中 
表示在这个树上从 到 的唯一路径上所有边的边权和。
强强和萌萌很好奇每次新长出一个叶子节点之后，这个树上总共有几对朋友。
我们假定这个树一开始为空，节点按照加入的顺序从 
开始编号。由于强强非常好奇，你必须在他每次出现新结点后马上给出总共的朋友对数，不能拖延哦。
【输入格式】
第一行包含一个整数，表示测试点编号。
第二行包含一个正整数 ，表示总共要加入的节点数。
我们令加入节点前的总共朋友对数是 
，在一开始时它的值为 
。
接下来 行中第 行有三个非负整数 
，表示结点 的父节点的编号为 
（其中 
表示异或，
表示取余，数据保证这样操作后得到的结果介于 到 
之间），与父结点之间的边权为 
，节点 上小精灵的感受能力值为 。
注意 
，表示 号节点是根结点，对于 
，父节点的编号至少为 。
【输出格式】
包含 行，每行输出 个整数，表示加入第 个点之后，树上有几对朋友。
【数据范围】
，
，
，
，时限 12s
这是 CTSC2014 一道陈老师的可怕题目！
露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是，由计算机生成的随机数序列并非真正的随机数，而是由一定法则生成的伪随机数。
某一天，露露了解了一种生成随机数的方法，称为 Mersenne twister。给定初始参数 
，
和初值 
，它通过下列递推式构造伪随机数列 
：
其中 是二进制异或运算（C/C++ 中的 ^ 运算）。而参数 
的选取若使得该数列在长度趋于无穷时，近似等概率地在 
中取值，就称 是好的。例如，在 
时 
就显然不是好的。
在露露向伙伴介绍了 Mersenne twister 之后，花花想用一些经典的随机性测试来检验它的随机性强度。为此，花花使用计算机计算了一些 
。
但细心的萱萱注意到，花花在某次使用二进制输入 
时，在末尾多输入了 
个 。她正想告诉花花这个疏忽，然而花花已经计算并记录了错误的 值而没有记录 的值。虽然这其实不是什么致命的问题，但是在萱萱告诉花花她的这个疏漏时，作为完美主义者的花花还是恳求萱萱帮她修正 的值。萱萱便把这个任务交给了他的 AI ——你！
【输入格式】
输入文件 random.in 的第一行包含一个正整数 
，第二行为二进制表示的 （共 个数，从低位到高位排列），第三行为二进制表示的 
（排列方式同 ），第四行包含一个整数 
。
接下来分为两种可能的情况：
（萱萱记下了花花的输入）：则第五行包含一个整数，表示萱萱记下来的正确的 值。
（萱萱未能记下花花的输入）：则第五行为 ，第六行输入花花计算出错误的二进制表示的 。【输出格式】
输出文件 random.out 仅一行，为一个 位的 01 串，表示你求得的正确的 （同样要求从低位到高位排列）
【数据范围】
对于 的部分，
对于 的部分，
， 是“好的”
每个数据点时限 20s，并且开启编译器优化
