Little Q is a great magician who has recently invented three types of magic spells that act on numbers. For a number $x$, the effects of these three spells are:

1. Increase $x$ by 1, i.e., $x$ becomes $x + 1$.
2. Decrease $x$ by 1, i.e., $x$ becomes $x - 1$. This operation can only be used when $x > 1$.
3. Choose a positive integer $k > 1$, and $x$ becomes $x \times k$.

Now, Little Q starts with the number $x = 1$, and he can perform at most $B$ magic operations to change the number.

Little Q wants to know, for each integer $n$ ($l \leq n \leq r$), how many magic operation sequences of length at most $B$ exist such that $x$ becomes $n$ after the sequence of operations. You only need to output the answers modulo $998244353$.

Two magic operations are considered different if and only if they are of different types, or if they are both type 3 and the chosen $k$ values are different.

A magic operation sequence is a sequence consisting of some (possibly zero) magic operations, and its length is the number of operations it contains. Two magic sequences are different if and only if they have different lengths or there exists a position where the operations differ.

Input

A single line containing three positive integers $l, r, B$ ($1 \leq l \leq r \leq 3\times 10^{9}, r - l \leq 30000, B \leq 100$).

Output

A single line containing $r - l + 1$ integers representing the answers. The $i$-th integer represents the number of ways to obtain $l+i-1$, modulo $998244353$.

Examples

Input 1

1 10 3

Output 1

4 10 11 13 14 16 15 18 19 16

Note 1

In the example, there are 4 magic sequences of length at most 3 that transform 1 to 1:

1. Empty sequence
2. +1, -1
3. ×2, -1
4. ×3, -1, -1

Subtasks

For $100\%$ of the data, $1 \leq l \leq r \leq 3 \times 10^9, r - l \leq 30000, 1 \leq B \leq 100$.

Subtask 1 ($6\%$): $r, B \le 10$

Subtask 2 ($18\%$): $r \leq 10^6, B \leq 40$

Subtask 3 ($8\%$): $r \leq 5 \times 10^6, B \leq 40$

Subtask 4 ($12\%$): $l = r, B \le 4$

Subtask 5 ($15\%$): $r \leq 10^{8}$

Subtask 6 ($23\%$): $r \leq 10^{9}$

Subtask 7 ($18\%$): No special restrictions.