Description

Jiutiao Keliansi is a girl who likes playing games. To improve her gaming skills, she wants to arm herself with theory. This problem is related to the famous Minimax search.

Keliansi has a rooted tree with the root numbered $1$. Define the depth of the root as $1$, and the depth of any other node as its parent’s depth plus $1$. Given the values on the leaf nodes, Keliansi defines the value of each non-leaf node as follows:

• For a non-leaf node at odd depth, its value is the maximum among the values of all its children.
• For a non-leaf node at even depth, its value is the minimum among the values of all its children.

At the beginning, Keliansi sets the value of the leaf node numbered $i$ to be $i$, and computes the root’s value as $W$.

Now, the evil Cedyks wants to change the root’s value by modifying the values of some leaf nodes. Cedyks has designed a quantum attacker. After it is activated, Cedyks will randomly gain control of a non-empty set of leaf nodes $S$, and can spend some energy to modify the values of the leaf nodes in $S$.

However, modifying leaf node values costs energy. For a leaf node $i \in S$, its initial value is $i$. Suppose Cedyks changes its value to $w_i$ ($w_i$ can be any integer, including negative numbers). Then the energy needed for this attack is $\max_{i\in S} |i − w_i|$.

Cedyks wants to save as much energy as possible, so he will always complete the attack with the minimum energy, i.e. under the minimum energy cost, make the root’s value change. Let $w(S)$ be the energy Cedyks will spend after gaining control of set $S$. In particular, for some sets $S$, no matter how the values of the leaf nodes in $S$ are changed, the root’s value will not change. In this case, $w(S)$ is defined as $n$. For convenience, we call $w(S)$ the stability of $S$.

When there are $m$ leaf nodes, there are $2^m − 1$ different non-empty sets of leaf nodes. Before launching the attack, Cedyks wants to estimate the energy he may need. So he gives an interval $[L, R]$, and wants to know, for each $k \in [L, R]$, how many sets $S$ satisfy $w(S) = k$.

Input Format

The first line contains three integers $n, L, R(n ≥ 2,1 \leq L \leq R \leq n)$.

The next $n - 1$ lines each contain two integers $u, v$, indicating an edge in the tree.

Output Format

Output one line with $R-L+1$ integers. The $i$-th integer indicates how many sets $S$ have $w(S) = L+i-1$. The answer may be very large; output it modulo $998244353$.

5 1 5
1 5
1 4
5 3
5 2

4 0 1 0 2

Hint

Explanation of Sample 1

At the beginning, under Keliansi’s setting (the value of leaf node $i$ is $i$), the root’s value is $4$.

There are $3$ leaf nodes $\{2,3,4\}$ in the tree, and there are $7$ non-empty sets of leaf nodes, among which:

• $\{4\}, \{2,4\}, \{3,4\}, \{2,3,4\}$ have stability $1$. As long as you slightly modify the value of leaf node $4$, the root’s value will change.
• $\{2\}, \{3\}$ have stability $5$, because the value at node $5$ is the smaller one between $2$ and $3$. If you only modify node $2$ or only modify node $3$, the value at node $5$ is always less than or equal to $3$, so the root’s value is always $4$.
• $\{2,3\}$ has stability $3$. To make the root’s value change, the value at node $5$ must be greater than $4$, so both $w_2$ and $w_3$ must be greater than $4$. Therefore the stability is $3$. One feasible plan is to set both $w_2$ and $w_3$ to $5$.

Constraints

For all testdata, it is guaranteed that $n\ge2$, $1\le L \le R \le n$.

Translated by ChatGPT 5