Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.

Each piece of tofu in the canteen is given a m-based number, all numbers are in the range $[l, r]$ ($l$ and $r$ being m-based numbers), and for every m-based integer in the range $[l, r]$, there exists a piece of tofu with that number.

To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.

Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?

Alice and Bob are playing with a magic tree This magic tree has $n$ nodes,with $n-1$ magic paths connecting them into a connected block. Node $1$ is at the top of the magic tree (layer $0$). Node $i$ is at the $k$th layer, where $k$ is the distance from the node $i$ to the node $1$. Alice and Bob give a mana value on each node. If a magic stone falls on node $i$, it will be sent up to the $k$ layer and appear on the $k$th ancestor node of the $i$ layer($k$ is the mana value of node $i$). This node will continue to send up it, and so on. If the layer of node $i$ is less than $k$, this stone will be sent out of the magic tree. Alice is curious, she will modify the magic value of a node, and ask Bob: If you drop a magic stone on the node $x$, how many times does it take to transfer it out of the magic tree?

Little Q is fighting against scary monsters in the game “Monster Hunter”. The battlefield consists of $n$ intersections, labeled by $1,2,…,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.

Chiaki has just learned hash in today’s lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Chiaki simply chooses a hash table of size $n$ with hash function $h(x) = x \mod n$.
Unfortunately, the hash function may map two distinct values to the same hash value. For example, when $n = 9$ we have $h(7) = h(16) = 7$. It will cause a failure in the procession of insertion. In this case, Chiaki will check whether the next position is available or not. This task will not be finished until an available position is found. If we insert $\lbrace 7, 8, 16 \rbrace$ into a hash table of size $9$, we will finally get $ \lbrace 16, -1, -1, -1, -1, -1, -1, 7, 8 \rbrace$. Available positions are marked as $-1$.
After done all the exercises, Chiaki became curious to the inverse problem. Can we rebuild the insertion sequence from a hash table? If there are multiple available insertion sequences, Chiaki would like to find the smallest one under lexicographical order.
Sequence $a_1, a_2, …, a_n$ is lexicographically smaller than sequence $b_1, b_2, …, b_n$ if and only if there exists $i$ ($1 ≤ i ≤ n$) satisfy that $a_i < b_i$ and $a_j = b_j$ for all $1 ≤ j < i$.

Chiaki has a sequence $A={a_1,a_2,\dots,a_n}$. Let $\mathbf{RMQ}(A, l, r)$ be the minimum $i$ ($l \le i \le r$) such that $a_i$ is the maximum value in $a_l, a_{l+1}, \dots, a_{r}$.

Two sequences $A$ and $B$ are called RMQ Similar, if they have the same length n and for every $1 \le l \le r \le n$, $\mathbf{RMQ}(A, l, r) = \mathbf{RMQ}(B, l, r)$.

For a given the sequence $A={a_1,a_2,\dots,a_n}$, define the weight of a sequence $B={b_1,b_2,\dots,b_n}$ be $\sum\limits_{i=1}^{n} b_i$ (i.e. the sum of all elements in $B$) if sequence $B$ and sequence $A$ are RMQ Similar, or $0$ otherwise. If each element of $B$ is a real number chosen independently and uniformly at random between $0$ and $1$, find the expected weight of $B$.

小团有一张$n$个点，$m$条边的无向图$G$，有些边上已经被标记了$0$或$1$，表示它的边权。
现在你需要给剩下的边标记边权为$0$或$1$，求有几种标记的方式满足：
对于G中任意一个环，里面所有边的边权的异或值为$0$。

环的定义如下：
对于任意$k$($k≥2$)个软件包$ \lbrace a_1,a_2,…,a_k \rbrace$，若对于所有的$i<k$满足$a_i$依赖$a_{i+1}$，且$a_1=a_k$成立，则这$k$个软件包构成一个环。

点点现在有$n$个软件包。他想设计一个软件包管理器。不可避免地，他要解决软件包之间的依赖问题。

一开始这些软件包之间没有依赖关系。但是每次点点会添加一条依赖关系$a$,$b$，表示软件包$a$依赖$b$。当这些软件包的依赖关系没有环的时候，那么这个软件包的管理器是好的，否则就是不好的。

环的定义如下：
对于任意$k$($k≥2$)个软件包$ \lbrace a_1,a_2,…,a_k \rbrace$，若对于所有的$i<k$满足$a_i$依赖$a_{i+1}$，且$a_1=a_k$成立，则这$k$个软件包构成一个环。

点点想让你回答他每次加入一条依赖关系之后这个软件包是不是好的，如果是好的那么输出$1$，否则输出$0$。同时，点点希望他在加入每一条关系之后你都能回答他，所以他会在读入中对数据进行加密。你只有回答了问题才能知道下一条依赖关系是什么。

Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.

Sonya lives in a city with $n$ junctions and $n - 1$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.

Sonya has exactly $k$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.

Sonya wants all her ice cream shops to form a simple path of the length $r$ ($1 \le r \le k$) , i.e. to be located in different junctions $f_1, f_2, \dots, f_r$ and there is street between $f_i$ and $f_{i+1}$ for each $1$ to $r - 1$.

The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $a$ and $b$ is equal to the sum of all the street lengths that you need to pass to get from the junction $a$ to the junction $b$. So Sonya wants to minimize
$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$
where $a$ takes a value of all possible $n$ junctions, $f_i$ — the junction where the $i$-th Sonya’s shop is located, and $d_{x,y}$ — the distance between the junctions $x$ and $y$.

Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $k$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.

What-The-Fatherland is a strange country! All phone numbers there are strings consisting of lowercase English letters. What is double strange that a phone number can be associated with several bears!

In that country there is a rock band called CF consisting of $n$ bears (including Mike) numbered from $1$ to $n$.

Phone number of $i$-th member of CF is $s_i$. May 17th is a holiday named Phone Calls day. In the last Phone Calls day, everyone called all the numbers that are substrings of his/her number (one may call some number several times). In particular, everyone called himself (that was really strange country).

Denote as $call(i, j)$ the number of times that $i$-th member of CF called the $j$-th member of CF.

The geek Mike has $q$ questions that he wants to ask you. In each question he gives you numbers $l$, $r$ and $k$ and you should tell him the number $$\sum_{i = l} ^ r call(i, k)$$