题目描述

给定一棵有根树的从左到右深度优先遍历记录。字符 D 表示从当前节点走向一个新儿子，字符 U 表示回到父亲。根节点至少有两个儿子；除根以外，每个非叶节点恰好有两个儿子。节点按照第一次被遍历到的顺序编号为 $0,1,\ldots,N-1$，其中根为 $0$。

根据 seed 生成序列 $a$：$a_0=seed$，对于 $i\ge 1$，$a_i=(a_{i-1}\times1103515245+12345)\bmod 2^{31}$。节点 $i$ 与其父亲之间的树边双向通行，代价为 $\left\lfloor a_i/2^{21}\right\rfloor$。

把所有叶子按照从左到右的顺序排列，并把这个顺序视为循环顺序。因此，每个叶子都有左右两个相邻叶子。除了沿树边移动，你还可以从一个叶子跳到循环顺序中与它相邻的叶子，每次跳跃代价均为 jumpCost。

你需要选择一个哈密顿环：恰好访问每个节点一次，最后回到起点。对于一个哈密顿环，我们记录访问的 $N$ 个节点，起点不会在末尾重复写一次。不同的起点或不同的方向会得到不同的序列，也视为不同答案。

将所有这些序列先按对应哈密顿环的总代价从小到大排序；总代价相同时，按节点序列的字典序排序。请输出排序后第 index 个序列，编号从 $1$ 开始。如果不存在第 index 个序列，则输出空序列。

输入格式

第一行一个字符串 dfs。

第二行三个整数 seed jumpCost index。

输出格式

第一行输出一个整数 $K$，表示答案序列长度。

如果第 index 个序列存在，则 $K=N$，第二行输出 $N$ 个整数，表示该序列。

如果不存在，则输出 $K=0$，之后无需输出其他内容。

数据范围

• $3\le N\le250$；
• dfs 长度为 $2(N-1)$，且一定描述一棵满足条件的树；
• $0\le seed<2^{31}$；
• $0\le jumpCost\le1023$；
• $1\le index\le10^9$。

样例 1

DUDU
47 500 3

3
1 0 2

样例 2

DUDU
47 500 7

0