There are $n$ planets, numbered $1$ to $n$, located within the same galaxy. This galaxy can be abstracted as a number line, where each planet is a point on the line. Specifically, the coordinate of the planet with number $i$ is $i$.

Initially, due to technological limitations, the inhabitants of these $n$ planets cannot communicate and are unaware of each other's existence. Now, these planets have independently developed tools for interstellar travel and communication. For the $i$-th planet, it successfully establishes contact with all planets with numbers in the range $[l_i, i-1]$ by emitting a powerful signal (the planet with number 1 does not emit any signal). Two planets that have established contact create a bidirectional portal. For two planets $u$ and $v$ connected by a portal, residents on $u$ can travel to $v$ in 1 unit of time, and residents on $v$ can travel to $u$ in 1 unit of time. We denote $dist(x, y)$ as the minimum time required to travel from planet $x$ to planet $y$ through a series of portals.

There are $q$ interstellar merchants. The $i$-th merchant is initially at position $x_i$, and their destination is one of the planets in the range $[l_i, r_i]$. It is guaranteed that $l_i < r_i < x_i$. The merchant chooses a planet $y$ from these planets with equal probability (each planet has the same probability of being chosen as the destination) and then travels to planet $y$ through a series of portals, spending the minimum amount of time. The merchant wants to know the expected time spent, which is calculated as $\frac{1}{r_i-l_i+1}{\sum_{y=l_i}^{r_i}{dist(x_i,y)}}$.

Input

The first line contains a positive integer $n$, representing the number of planets.

The second line contains $n-1$ positive integers. The $i$-th integer is $l_{i+1}$, indicating that all planets in the range $[l_{i+1}, i]$ have established contact with the planet numbered $i+1$, and travel between them costs 1 unit of time. It is guaranteed that $l_{i+1} \leq i$.

The third line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain three integers $l_i, r_i, x_i$, representing the expected value of $dist(x_i, y)$ when choosing a planet $y$ from the range $[l_i, r_i]$ with equal probability. It is guaranteed that $l_i < r_i < x_i$.

Output

For each query, note that the answer is always a rational number. Output this rational number in the format $p/q$, such that $gcd(p, q) = 1$.

If the answer is an integer $m$, output $m/1$.

Examples

Input 1

7
1 1 2 1 4 6
5
3 4 6
1 5 7
1 2 4
1 2 6
1 3 5

Output 1

3/2
13/5
3/2
2/1
1/1

Note 1

The undirected graph corresponding to the example is as follows:

Subtasks

For $20\%$ of the data, $n \leq 100$.

For another $25\%$ of the data, $n \leq 2000$.

For another $25\%$ of the data, $n \leq 5000$.

For $100\%$ of the data, $n, q \leq 3 \times 10^5$.