# 数位合并的最大值与最小值

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一座数字展馆有一块可合并数位的显示板。管理员希望知道，只操作一次，显示的数最大和最小能变成多少。

(本故事由GPT-6重写)

## 形式化问题描述

给定一个有 $n$ 位的 $k$ 进制正整数，数位从高到低为 $a_1,\ldots,a_n$ .恰好选择一次两个位置 $i<j$ ，令 $s=a_i+a_j$ ，并同时执行以下操作：

- 若 $s\ge k$ ，将位置 $i$ 的数字改为一、位置 $j$ 的数字改为 $s-k$ ，其他位置不变。
- 若 $s<k$ ，删除位置 $i$ ，将原位置 $j$ 的数字改为 $s$ .其余数位保持相对顺序。删除数位会缩短数字，并非把该位改成零。

最后删除所有前导零。分别求可能得到的最大整数和最小整数。两项答案可以使用不同的两个位置。

## 输入格式

第一行两个整数 $n,k$ .第二行 $n$ 个以十进制书写、用空格分隔的整数 $a_1,\ldots,a_n$ ，其中 $a_1$ 是最高位。

## 输出格式

输出两行，依次表示最大值和最小值。每行从高到低输出结果的各个 $k$ 进制数位；每个数位以十进制整数书写，相邻数位用一个空格分隔，不输出前导零。

## 样例

### 样例 1

### 输入

```text
4 10
1 8 9 9
```

### 输出

```text
1 8 9 0
9 9 9
```

### 样例 2

### 输入

```text
5 10
7 0 0 1 1
```

### 输出

```text
7 0 1 1
1 8
```

### 样例 3

### 输入

```text
3 10
1 2 3
```

### 输出

```text
3 3
1 5
```

## 样例解释

样例一最大值合并第一位和第四位，原来的最高位一保持不变，最低位变成零。最小值合并第一位和第二位，得到三个九。样例二的最小值合并第一位与第五位，删除最高位和随后的两个前导零，得到 $1,8$ .样例三没有任何数位对会进位。

## 数据范围与保证

$2\le n\le10^6$ , $2\le k\le10^9$ , $1\le a_1<k$ , $0\le a_i<k$ . 输入字符总数不超过 $21\times10^6$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |