四方棋（Quad Kingdoms Chess，简称 QKC）在 THU（技术锤子大学）的 605A 宿舍非常流行。

小青鱼在那所伟大的大学里有很多朋友。今天，在漫长的一天课程结束后，小 X 和小 Y 决定玩一局 QKC。

图 8：准备进行四方棋游戏

不幸的是，他们没能凑齐四个人——小青鱼根本不知道怎么玩！所以，为了找点乐子，他们各自随机抓取了一组棋子，开始了一场简单的棋子强度比拼游戏。简化后的游戏规则如下：

每个棋子由一个整数 $s_i \in [1, 10^5]$ 表示。小 X 和小 Y 各自拥有一组棋子。随后，比赛按照以下规则进行：

1. 最初，两位玩家将各自的棋子排列成一个序列，然后将序列进行均匀随机洗牌。
2. 接着，两位玩家部署各自序列中的第一枚棋子，记小 X 的棋子为 $x$，小 Y 的棋子为 $y$。
3. 若 $x > y$，小 Y 的棋子被淘汰，他必须部署序列中的下一枚棋子。
4. 若 $x < y$，小 X 的棋子被淘汰，他必须部署序列中的下一枚棋子。
5. 若 $x = y$，两枚棋子同时被淘汰，两位玩家均需部署序列中的下一枚棋子。

如果在任何时刻，一名玩家无法部署棋子，而另一名玩家至少还有一枚棋子，则剩余棋子的玩家获胜；如果两位玩家同时耗尽棋子，则游戏平局。

小青鱼发现这个游戏太简单了！因此，在洗牌之前，他偷偷在小 X 的收藏中插入了 $k$ 枚额外的炸弹（也就是说，小 X 现在有 $n + k$ 枚棋子，其中 $n$ 枚是普通棋子，$k$ 枚是炸弹）。在游戏中，炸弹与任何棋子对战时总是会导致双方同时被淘汰。

给定两位玩家的棋子集合，小青鱼想知道游戏以小 X 获胜、小 Y 获胜或平局结束的概率，结果对 $998\,244\,353$ 取模。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m \le 1000, 0 \le k \le 20$)，分别表示小 X 拥有的普通棋子数量、小 Y 拥有的棋子数量，以及小青鱼插入的炸弹数量。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，表示小 X 的普通棋子大小。

输入的第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_j \le 10^5$)，表示小 Y 的棋子大小。

输出格式

输出的第一行包含一个整数 $P_X$，表示小 X 获胜的概率，对 $998\,244\,353$ 取模。

输出的第二行包含一个整数 $P_Y$，表示小 Y 获胜的概率，对 $998\,244\,353$ 取模。

输出的第三行包含一个整数 $P_=$，表示平局的概率，对 $998\,244\,353$ 取模。

样例

输入 1

5 5 1
11 4 2 11 9
20 1 6 20 1

输出 1

0
1
0

输入 2

8 7 5
58 42 34 58 12 12 9 1
28 59 59 1 36 14 7

输出 2

695057094
239873545
63313715

输入 3

8 7 5
9 1 2 12 7 7 7 6
15 4 15 1 15 11 13

输出 3

673575784
13961460
310707110