这个问题与前一个问题的不同之处仅在于没有对所有数字 $$$a_1, a_2, \dots, a_n$$$ 的相等长度进行约束。
SIS 的一队学生将乘坐潜艇进行旅行。他们的目标是大雷宾斯克海底一艘沉船上的古代宝藏。不幸的是,学生们不知道船的坐标,所以他们请Meshanya(一位遗传法师)来帮助他们。他同意帮助他们,但前提是他们能解决他的问题。
让我们表示一个交替两个数字 $$$f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)$$$ 的函数,其中 $$$a_1 \dots a_p$$$ 和 $$$b_1 \dots b_q$$$ 是两个整数的数字以十进制表示法表示,不带前导零。
换句话说,函数 $$$f(x, y)$$$ 交替地打乱数字 $$$x$$$ 和 $$$y$$$ 的数字,从数字 $$$y$$$ 开始,从最低数字到较旧的数字。该函数的结果也是从右到左构建的(即从较低的数字到较旧的数字)。如果其中一个参数的数字已结束,则写出另一个参数的剩余数字。熟悉下面函数的示例和正式定义。
例如: $$$$$$f(1111, 2222) = 12121212$$$$$$ $$$$$$f(7777, 888) = 7787878$$$$$$ $$$$$$f(33, 44444) = 4443434$$$$$$ $$$$$$f(555, 6) = 5556$$$$$$$$$$$$f(111, 2222) = 2121212$$$$$$
正式地,
- 如果 $$$p \ge q$$$ 则 $$$f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$;
- 如果 $$$p < q$$$ 则 $$$f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$。
Mishanya 给你一个由 $$$n$$$ 整数 $$$a_i$$$ 组成的数组,你的任务是帮助学生计算 $$$\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)$$$ 模 $$$998\,244\,353$$$。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 数组中的元素数量。输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。
输出
打印以 $$$998\,244\,353$$$ 为模的答案。
示例
输入 #1
3 12 3 45
输出 #1
12330
输入 #2
2 123 456
输出 #2
1115598