Ranking Preservation Under Score Doubling Accident

In a contest with n participants, each participant i is estimated to score \(A_i\) (a non‐negative integer). The ranking of a participant is defined as the number of contestants whose score is at least his score (including himself). For example, if there are 3 contestants with scores \([1,2,2]\), their rankings are \([3,2,2]\) respectively.

On the contest day, an unforeseen accident (say, an alien attack) causes exactly k participants to have their scores doubled. Although you (the omniscient organizer) know the estimated scores, you don’t know which contestants are affected. If no accident occurred, the final scores would be \(A_i\) for all i, and the original ranking of participant i would be \(R_i^0 = 1 + |\{j: A_j > A_i\}| + |\{j: A_j = A_i, j\neq i\}|\).

After the accident, each contestant’s final score becomes:

[ F_i = \begin{cases} A_i, & \text{if contestant } i \text{ is not affected},\ 2A_i, & \text{if contestant } i \text{ is affected}. \end{cases} ]

The new ranking for contestant i is defined as the number of contestants whose final score is at least \(F_i\). For each participant i, count the number of ways (i.e. choices of exactly k contestants to have their scores doubled) for which participant i's ranking remains unchanged, i.e. the new ranking equals \(R_i^0\). As the answer can be huge, output it modulo \(998244353\).

Details

Let the contestants be divided into groups relative to a fixed contestant i with score \(A_i\):

• Group G: contestants with \(A_j > A_i\). For any \(j \in G\), regardless of whether they are affected, \(F_j > F_i\) if \(i\) is not affected and \(F_j > 2A_i\) if \(i\) is affected.
• Group F: contestants with \(A_j = A_i\) (and \(j \neq i\)). Their contribution depends on whether they are doubled and whether \(i\) is doubled.
• Group L: contestants with \(A_j < A_i\). This group is further partitioned into:
  • L_valid: those with \(2A_j \ge A_i\) (if \(i\) is not affected, if such a contestant is doubled it could threaten the ranking).
  • L_invalid: those with \(2A_j < A_i\) (their status does not affect the ranking of \(i\)).

There are two cases to consider for contestant i:

1. i not affected (i.e. \(F_i=A_i\)). In this case, to have the ranking preserved, no contestant in L_valid can be affected. Other contestants may be arbitrarily doubled provided that exactly k contestants (out of all n) are affected.
2. i affected (i.e. \(F_i=2A_i\)). In this case, among the contestants in Group F (with \(A_j=A_i\)), they must be affected to ensure their final scores remain \(2A_i\) (so that they count towards the ranking of \(i\)).

Let:

[ \begin{aligned} G &= |{j: A_j > A_i}|,\ E &= |{j: A_j = A_i}| - 1,\ L &= |{j: A_j < A_i}|,\ L_{valid} &= |{j: A_j < A_i \text{ and } 2A_j \ge A_i}|,\ L_{invalid} &= L - L_{valid}. \end{aligned} ]

Then the original ranking is \(R_i^0 = 1 + G + E\). Define:

• Case 1 (i not affected): The free contestants (where choices are allowed) are those in Group G, Group F and L_invalid. Let \(free_1 = G + E + L_{invalid}\). The number of valid accident scenarios is \(C(free_1, k)\) (provided \(k\) does not exceed \(free_1\)).
• Case 2 (i affected): In this scenario, contestant i is forced to be in the affected set, and all contestants in Group F must also be affected. Let the forced count be \(1 + E\). The free group consists of contestants in Group G and Group L, with size \(free_2 = G + L\). Then the contribution is \(C(free_2, k - (1+E))\) (if \(k-(1+E)\) is within \([0,free_2]\)).

The answer for contestant i is the sum of the valid selections from the two cases modulo \(998244353\).

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 2×10⁵, 0 ≤ k ≤ n), denoting the number of contestants and the number of contestants whose score is doubled.

The second line contains n non‐negative integers \(A_1, A_2, \dots, A_n\), where \(0 \le A_i \le 10^9\), representing the estimated scores.

outputFormat

Output n integers separated by spaces, where the i-th integer is the number of ways (modulo \(998244353\)) to select exactly k contestants such that the ranking of contestant i remains unchanged.

sample

3 1
1 2 2

3 1 1