Expected Damage

题意翻译

你在玩电脑游戏，在这个游戏中，你必须和$n$个怪物战斗。 为了防御怪物，你需要一个盾牌。每个盾牌有两个参数：盾牌耐久度$a$和防御等级$b$。每个怪物只有一个参数：力量$d$。 当你拥有耐久度a和防御等级b的盾牌，与一个力量为d的怪物对抗时，有三种可能的结果： 如果$a=0$，则受到$d$伤害； 如果$a>0$且$d≥b$，你不会受到伤害，但是护盾的当前耐久度降低1； 如果$a>0$且$d<b$，则不会发生任何事情。 第$i$个怪物有力量$di$，你将以随机顺序与每个怪物战斗一次（所有$n!$个顺序的出现概率是均等的）。你将考虑$m$个不同的盾牌，第$i$个盾牌有初始耐久度$ai$和防御等级$bi$。对于每一个盾牌，计算如果你拿着这个盾牌与给定的$n$个怪物随机战斗，你将受到的预期伤害。

题目描述

You are playing a computer game. In this game, you have to fight $ n $ monsters. To defend from monsters, you need a shield. Each shield has two parameters: its current durability $ a $ and its defence rating $ b $ . Each monster has only one parameter: its strength $ d $ . When you fight a monster with strength $ d $ while having a shield with current durability $ a $ and defence $ b $ , there are three possible outcomes: - if $ a = 0 $ , then you receive $ d $ damage; - if $ a > 0 $ and $ d \ge b $ , you receive no damage, but the current durability of the shield decreases by $ 1 $ ; - if $ a > 0 $ and $ d < b $ , nothing happens. The $ i $ -th monster has strength $ d_i $ , and you will fight each of the monsters exactly once, in some random order (all $ n! $ orders are equiprobable). You have to consider $ m $ different shields, the $ i $ -th shield has initial durability $ a_i $ and defence rating $ b_i $ . For each shield, calculate the expected amount of damage you will receive if you take this shield and fight the given $ n $ monsters in random order.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 2 \cdot 10^5 $ ) — the number of monsters and the number of shields, respectively. The second line contains $ n $ integers $ d_1 $ , $ d_2 $ , ..., $ d_n $ ( $ 1 \le d_i \le 10^9 $ ), where $ d_i $ is the strength of the $ i $ -th monster. Then $ m $ lines follow, the $ i $ -th of them contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i \le n $ ; $ 1 \le b_i \le 10^9 $ ) — the description of the $ i $ -th shield.

输出格式

Print $ m $ integers, where the $ i $ -th integer represents the expected damage you receive with the $ i $ -th shield as follows: it can be proven that, for each shield, the expected damage is an irreducible fraction $ \dfrac{x}{y} $ , where $ y $ is coprime with $ 998244353 $ . You have to print the value of $ x \cdot y^{-1} \bmod 998244353 $ , where $ y^{-1} $ is the inverse element for $ y $ ( $ y \cdot y^{-1} \bmod 998244353 = 1 $ ).

输入输出样例

输入样例 #1

3 2
1 3 1
2 1
1 2

输出样例 #1

665496237
1

输入样例 #2

3 3
4 2 6
3 1
1 2
2 3

输出样例 #2

0
8
665496236

题意翻译

你在玩电脑游戏，在这个游戏中，你必须和$n$个怪物战斗。 为了防御怪物，你需要一个盾牌。每个盾牌有两个参数：盾牌耐久度$a$和防御等级$b$。每个怪物只有一个参数：力量$d$。 当你拥有耐久度a和防御等级b的盾牌，与一个力量为d的怪物对抗时，有三种可能的结果： 如果$a=0$，则受到$d$伤害； 如果$a>0$且$d≥b$，你不会受到伤害，但是护盾的当前耐久度降低1； 如果$a>0$且$d<b$，则不会发生任何事情。 第$i$个怪物有力量$di$，你将以随机顺序与每个怪物战斗一次（所有$n!$个顺序的出现概率是均等的）。你将考虑$m$个不同的盾牌，第$i$个盾牌有初始耐久度$ai$和防御等级$bi$。对于每一个盾牌，计算如果你拿着这个盾牌与给定的$n$个怪物随机战斗，你将受到的预期伤害。