CF1195D2.Submarine in the Rybinsk Sea (hard edition)

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$$

Formally,

• 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$;
• if $p \lt 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$.

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$.

本题与前一题的唯一区别在于，取消了所有数字 $a_1, a_2, \dots, a_n$ 长度相等的约束条件。

一支 SIS 学生队伍计划乘坐潜艇进行一次探险。他们的目标是位于大雷宾斯克海海底一艘沉船中的古代宝藏。不幸的是，学生们并不知道该沉船的坐标，因此他们请求梅沙尼亚（一位世袭魔法师）协助。他同意帮忙，但前提是学生们必须先解决他提出的问题。

我们定义一个函数 $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 \lt 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$。

梅沙尼亚给你一个由 $n$ 个整数 $a_i$ 构成的数组。你的任务是帮助学生们计算

$$\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)$$

对 $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.

输入的第一行包含一个整数 $n$（$1 \le n \le 100\,000$）—— 表示数组中元素的个数。
输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组的元素。

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

将答案对 $998\,244\,353$ 取模后输出。