题目描述

一把锁由上下两条写有大写英文字母的循环纸带组成。第一条纸带长度为 $N$，第二条长度为 $M$，且 $M<N$。每次操作可以把任意一条纸带向左或向右循环移动一个字符。

开锁过程分为两步：

1. 先循环移动第二条纸带，使得到的字符串在所有循环移位中字典序最小；
2. 再循环移动第一条纸带，使它的前 $M$ 个字符与第二条纸带当前字符串相比，至多有一个位置不同。

题目保证存在可行方案。

如果第一条纸带有多种可行移动方式，应选择移动次数最少的；若最少次数下向左和向右都可行，则选择向左移动。

输入格式

第一行两个整数 $N,M$，满足：

$1\le M<N\le10^6$。

第二行一个长度为 $N$ 的大写英文字母串，表示第一条纸带。

第三行一个长度为 $M$ 的大写英文字母串，表示第二条纸带。

输出格式

输出两行：

• 第一行：第二条纸带经过第一步后的字符串；
• 第二行：第一条纸带按题意选择的最终字符串。

样例

输入

7 4
KADABRA
ABRA

输出

AABR
DABRAKA