给定长度为 $n$ 的整数序列 $h[n]$ ，有 $Q$ 个询问，每次给出 $l_1,r_1$ ，​询问有多少对 $l_2,r_2$ ，满足以下条件:

1. $r_2 – l_2 = r_1 – l_1$
2. 区间 $[l_1, r_1]$ 与区间 $[l_2, r_2]$ 没有交集
3. 对于任意 $i \in [0,r_1 – l_1]$ ，满足 $h[l_1 + i] + h[l_2 + i] = h[l_1] + h[l_2]$

给定一个 $n$ 个节点的有根树，开始时每个节点的权值都为 $0$ 。一共有 $q$ 个时刻，每个时刻可能有如下两个操作之一：

1. 给定一个节点 $x$ ，从下一个时刻起每个时刻都给该节点的权值 $+1$（每个节点只会有一次该操作）；

2. 给定两个节点 $x,y$ 以及一个数 $C$ ，求这两个节点的简单路径上权值大于 $C$ 的节点个数，以及简单路径上的所有节点个数。

可持久化线段树，是一种可以进行可持久化操作的线段树，具有优越的时间复杂度。

给一个数列 ${a_n}$ ，每次询问区间 $[l,r]$ 内有没有一个数出现次数超过一半。如果有，输出这个数，如果没有，输出 $0$ 。