题目描述

给定一个字符串 s，使用递归打印出它的所有排列。

输入格式

一个字符串 s（长度不超过8）

输出格式

按字典序打印出所有排列，每个排列占一行

示例

输入

ABC

输出

ABC
ACB
BAC
BCA
CAB
CBA