Mario works at a factory. There are $n$ pipes in a row. Let us label the pipes $1, 2, 3,\ldots, n$ from left to right. The factory will deliver $a_i$ units of water per second through pipe $i$ for $i$ from $1$ to $n$. His job is to open some consecutive pipes to make them output exactly $j$ units of water per second, but he doesn't know how to do it. Help Mario to find which segment of pipes to open.
You are given $a_1, a_2, a_3, \ldots,a_n$. Let $s=\sum\limits_{i=1}^{n}a_i$. Your task is to find $(l_j, r_j)$ for all $j$ from $1$ to $s$ such that $j=a_{l_j}+a_{l_{j}+1}+\ldots +a_{r_j}$. Because of his boss' command, if there are $k$ possible $(l, r)$ for $j$, then $(l_j, r_j)$ is the $\lfloor \dfrac{k+1}{2} \rfloor$-th smallest one of all possible $(l, r)$. If there are no possible $(l,r)$ for $j$, then $(l_j, r_j)=(0, 0)$.
We say $(x, y)$ is smaller than $(z, w)$ if $x<z$ or ( $x=z$ and $y<w$ ).
For example, $n=4$ and ($a_1$, $a_2$, $a_3$, $a_4$)$=$($2$, $1$, $1$, $2$), then we can find ($(l_1,r_1)$, $(l_2,r_2)$, $(l_3,r_3)$, $(l_4,r_4)$, $(l_5,r_5)$, $(l_6,r_6)$)$=$($(2,2)$, $(2,3)$, $(1,2)$, $(1,3)$, $(0,0)$, $(1,4)$).
There are $2$ possible $(l,r)$ for $1$ which are $(2,2),(3,3)$ and $(l_1,r_1)$ is the $1$-th smallest, so $(l_1,r_1)=(2,2)$.
There are $3$ possible $(l,r)$ for $2$ which are $(1,1),(2,3),(4,4)$ and $(l_2,r_2)$ is the $2$-th smallest, so $(l_2,r_2)=(2,3)$.
There are $2$ possible $(l,r)$ for $3$ which are $(1,2),(3,4)$ and $(l_3,r_3)$ is the $1$-th smallest, so $(l_3,r_3)=(1,2)$.
There are $2$ possible $(l,r)$ for $4$ which are $(1,3),(2,4)$ and $(l_4,r_4)$ is the $1$-th smallest, so $(l_4,r_4)=(1,3)$.
There are no possible $(l,r)$ for $5$, so $(l_5,r_5)=(0,0)$.
There is $1$ possible $(l,r)$ for $6$ which is $(1,4)$ and $(l_6,r_6)$ is the $1$-th smallest, so $(l_6,r_6)=(1,4)$.