二进制数是计算机科学的基础。大多数人都听说过其他进制系统，例如三进制、八进制或十六进制。你可能知道如何使用这些系统以及如何在它们之间进行转换。但你是否知道，进制的基数（radix）也可以是负数？捷克理工大学的一位助理教授最近接触到了负二进制数以及其他负基数系统。你能帮他实现这些进制系统与十进制之间的相互转换吗？

在正基数 $R$ 的系统下，一个数 $N$ 总是表示为由 $0$ 到 $R - 1$（含）之间的数字组成的字符串。位置 $P$（位置从右往左数，且从零开始）上的数字代表 $R^P$ 的权重。这意味着该位置上的数字乘以 $R^P$，然后将所有位置的值相加。例如，如果使用八进制系统（基数 $R = 8$），表示为 $17024$ 的数的值为：

$$1 \cdot 8^4 + 7 \cdot 8^3 + 0 \cdot 8^2 + 2 \cdot 8^1 + 4 \cdot 8^0 = 1 \cdot 4096 + 7 \cdot 512 + 0 \cdot 64 + 2 \cdot 8 + 4 \cdot 1 = 7700$$

对于负基数 $-R$，原理是相同的：每个位置上的数字代表 $(-R)^P$ 的权重。例如，一个负八进制（基数 $R = -8$）数 $17024$ 的值为：

$$1 \cdot (-8)^4 + 7 \cdot (-8)^3 + 0 \cdot (-8)^2 + 2 \cdot (-8)^1 + 4 \cdot (-8)^0 = 1 \cdot 4096 + 7 \cdot (-512) + 0 \cdot 64 + 2 \cdot (-8) + 4 \cdot 1 = 500$$

负基数系统的一个巨大优势是我们不需要负号来表示负数。以下是负二进制系统（$R = -2$）的一些例子：

你可能会注意到，如果不允许“前导零”，任何整数的负二进制表示都是唯一的。唯一可以以数字“0”开头的数只有零本身。

输入格式

输入将包含多次转换，每次转换占一行。

从十进制系统转换到某种负基数系统的转换将以小写单词 to 开头，紧接着一个负号（其前无空格）、要求的基数 $R$、一个空格，以及一个十进制数 $N$。

转换到十进制系统的转换将以小写单词 from 开头，紧接着一个负号、基数 $R$、一个空格，以及一个在基数为 $-R$ 的系统下表示的数。

输入将以包含小写单词 end 的行结束。所有数字均满足以下条件：$2 \le R \le 10$，$-1\,000\,000 \le N \le 1\,000\,000$（十进制）。

输出格式

对于每次转换，在单独的一行中输出一个数。如果输入使用的是十进制格式，则输出该数在基数为 $-R$ 的系统下的表示。如果输入包含这样一个负基数表示的数，则输出其十进制值。

输入和输出的数字都不能包含任何前导零。负号 - 仅能出现在以十进制系统表示的负数中。任何非负数或在负基数系统下表示的数都不能以负号开头。

样例

输入样例 1

to-2 10
from-2 1010
to-10 10
to-10 -10
from-10 10
end

输出样例 1

11110
-10
190
10
-10