Submarine in the Rybinsk Sea (hard edition)

### 题目描述 这题与上一个题的不同之处仅在于存在使所有数字 $a_1,a_2,\dots,a_n$ 的无长度相等的约束。 $SIS$ 学生团队将乘坐潜水艇去旅游，他们的目标是位于大雷宾斯克 $(Rybinsk)$ 海底沉船中的古代宝藏。不幸的是，学生们不知道船的坐标，因此他们要求 $Meshanya$（一位世袭魔法师）来帮助他们。$Meshanya$ 同意帮助他们，但前提是他们得解决了 $Meshanya$ 的问题。 让我们用一个函数 $f(a_1a_2\dots a_{p-1}a_p,b_1b_2\dots b_{p-1}b_p)$ 来交替两个数字的各位数码，其中 $a_1,a_2,\dots,a_p$ 和 $b_1,b_2,\dots,b_p$ 是以十进制表示的两个整数的数码，不含前导零。 换句话说，函数 $f(x,y)$ 通过将数字 $x$ 和 $y$ 的各位数码从最低位数写到较高位数字，从数字 $y$ 开始，交替地插入数字 $x$ 和 $y$。该函数的结果也是从右到左构建的（即从较低的数字到较旧的数字）。如果其中一个参数（不妨设为 $x$）的数字已写完，则写下另一个参数（即 $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)_{(10)}$ $Mishanya$ 为您提供一个由 $n$ 个整数组成的数组 $\{a_i\}$。你的任务是帮助学生们计算 $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} f(a_i, a_j) \mod 998244353$ ### 输入格式 输入的第一行包含一个整数 $n(1 \le n \le 100000)$。输入的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n(1\le a_i\le10^9)$，所有数字长度相同，它们即位数相等。 ### 输出格式 答案模 $998244353$。

This problem differs from the previous one only in the absence of the constraint on the equal length of all numbers $ a_1, a_2, \dots, a_n $ . A team of SIS students is going to make a trip on a submarine. Their target is an ancient treasure in a sunken ship lying on the bottom of the Great Rybinsk sea. Unfortunately, the students don't know the coordinates of the ship, so they asked Meshanya (who is a hereditary mage) to help them. He agreed to help them, but only if they solve his problem. Let's denote a function that alternates digits of two numbers $ f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q) $ , where $ a_1 \dots a_p $ and $ b_1 \dots b_q $ are digits of two integers written in the decimal notation without leading zeros. In other words, the function $ f(x, y) $ alternately shuffles the digits of the numbers $ x $ and $ y $ by writing them from the lowest digits to the older ones, starting with the number $ y $ . The result of the function is also built from right to left (that is, from the lower digits to the older ones). If the digits of one of the arguments have ended, then the remaining digits of the other argument are written out. Familiarize with examples and formal definitions of the function below. For example: $ $$$f(1111, 2222) = 12121212 $ $ $ $ f(7777, 888) = 7787878 $ $ $ $ f(33, 44444) = 4443434 $ $ $ $ f(555, 6) = 5556 $ $ $ $ f(111, 2222) = 2121212 $ $ </p><p>Formally,</p><ul> <li> if $ p \\ge q $ then $ 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 $ ; </li><li> if $ p < q $ then $ 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 $ . </li></ul><p>Mishanya gives you an array consisting of $ n $ integers $ a\_i $ , your task is to help students to calculate $ \\sum\_{i = 1}^{n}\\sum\_{j = 1}^{n} f(a\_i, a\_j) $ modulo $ 998\\,244\\,353$$$.

The first line of the input contains a single integer $ n $ ( $ 1 \le n \le 100\,000 $ ) — the number of elements in the array. The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array.

Print the answer modulo $ 998\,244\,353 $ .

3
12 3 45

12330

2
123 456

1115598