Description

Little C is the organizer of a well-known contest. There are $n$ contestants in total, and each contestant's score is a non-negative integer. Define a contestant's rank as: the number of contestants whose scores are not less than theirs (including themselves). For example, if the scores of $3$ contestants are $[1, 2, 2]$, then their ranks are $[3, 2, 2]$.

With a god's-eye view, you know all contestants' abilities, so before the contest you accurately estimated everyone's score. Let your estimated score for the $i$-th contestant be $A_i$. Since you have a god's-eye view, if nothing unexpected happens, your estimated scores will be the contestants' final scores.

However, on the contest day an irresistible accident happened (for example, an alien attack), causing some contestants' scores to become twice their final scores. Even with a god's-eye view, you do not know exactly which contestants' scores were doubled. The only information you know is that there are exactly $k$ such contestants.

Now you need to compute, after the accident, for the $i$-th contestant, how many scenarios make their rank unchanged.

Since the answer may be too large, you only need to output the answer modulo $998244353$.

Input Format

The first line contains two positive integers $n, k$.

The second line contains $n$ non-negative integers $A_1, A_2, \cdots, A_n$.

Output Format

Output $n$ lines. The $i$-th line contains a non-negative integer $ans_i$, representing the number of scenarios in which the $i$-th contestant's rank does not change after the accident.

3 2
1 2 3

3
1
2

Hint

• For $10\%$ of the testdata, $1 \leq n \leq 15$.
• For $35\%$ of the testdata, $1 \leq n \leq 10^3$.
• Another $10\%$ of the testdata satisfies that all scores are pairwise distinct.
• Another $10\%$ of the testdata satisfies $0 \leq A_i \leq 10^5$.
• Another $10\%$ of the testdata satisfies $k = 85$, $0 \leq A_i \leq 600$.
• For $100\%$ of the testdata, $1 \leq k < n \leq 10^5$, $0 \leq A_i \leq 10^9$.

Translated by ChatGPT 5