Little C is the organizer of a well-known competition with $n$ participants. Each participant's score is a non-negative integer. A participant's rank is defined as the number of participants whose scores are greater than or equal to their own (including themselves). For example, if the scores of 3 participants are $[1, 2, 2]$, their ranks are $[3, 2, 2]$.

Possessing a god's-eye view, you know the ability of all participants and have accurately estimated each person's score before the exam. Let $A_i$ be your estimated score for the $i$-th participant. Because you have a god's-eye view, these estimates would be the final scores if no accidents occurred.

However, an unavoidable accident occurred on the day of the competition (e.g., an alien attack), causing the scores of some participants to double. Even with your god's-eye view, you do not know exactly which participants' scores doubled; the only information you have is that there are exactly $k$ such participants.

Now, you need to calculate, for each participant $i$, how many scenarios exist where their rank remains unchanged after the accident.

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

Input

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

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

Output

Output $n$ lines, where the $i$-th line contains a non-negative integer $ans_i$, representing the number of scenarios where the rank of the $i$-th participant remains unchanged after the accident.

Examples

Input 1

3 2
1 2 3

Output 1

3
1
2

Note 1

There are 3 possible scenarios: (1, 2) double, (1, 3) double, and (2, 3) double.

For the first participant, even if their score doubles, everyone else's score remains greater than or equal to theirs, so their rank never changes in any scenario.

For the second participant, if (1, 2) double, the scores become (2, 4, 3), and their rank becomes first; if (1, 3) double, the scores become (2, 2, 6), and their rank becomes third; if (2, 3) double, the scores become (1, 4, 6), and their rank remains second. Thus, there is only one scenario where their rank is unchanged.

For the third participant, if (1, 2) double, their rank becomes second; in all other scenarios, it remains first.

Subtasks

For $10\%$ of the data, $1 \leq n \leq 15$.

For $35\%$ of the data, $1 \leq n \leq 10^3$.

An additional $10\%$ of the data satisfies the condition that all participants' scores are distinct.

An additional $10\%$ of the data satisfies $0 \leq A_i \leq 10^5$.

An additional $10\%$ of the data satisfies $k = 85$ and $0 \leq A_i \leq 600$.

For $100\%$ of the data, $1 \leq k < n \leq 10^5$ and $0 \leq A_i \leq 10^9$.