EOJ-自适应编程学习平台

在采用进位计数的数字系统中，如果使用的数码依次为 $0,1,2,\ldots,R-1$，总共 $R$ 个数码，则称其为基 $R$ 数制或 $R$ 进制。$R$ 称为该数制的“基数”($Radix$)，例如，十进制的基数是 $10$（数码为： $0,1,2,\ldots,9$），二进制的基数是 $2$（数码为： $0,1$），八进制的基数是 $8$（数码为： $0,1,2,\ldots,7$）。

现有一种特殊的按位计数系统，该系统采用的基数为复数 $-1+i$（其中 $i$ 表示 $\sqrt{-1}$ ）。在$-1+i$ 进制系统中，所有“复数整数”（实部和虚部都为整数的复数，这种复数在数学上称为高斯整数）都可以表示成一个“数”，该“数”只含有 $0,1$ 两个数码，不需要正负符号或其他常规手段，而且每个“复数整数”只有唯一一种表示方法。例如：整数 $2$ 用 $-1+i$ 进制表示出来是1100。

任意一个“复数整数” $a+bi$ （$a,b$ 均为整数） 可采用如下算法转换为$-1+i$ 进制表示：

1、$a+bi$ 除以 $-1+i$ 得到商 $q$ 和余数 $r$ ，商$q$ 也为“复数整数”，余数 $r$ 为 $0$ 或 $1$。

​ 令 $q=q_r+q_ii$ （$q_r$ 与 $q_i$ 均为整数，分别表示商 $q$ 的实部与虚部），

​ $q,r$ 必满足下式： $a+bi= (q_r+q_ii)(-1+i) + r$

​ 如果 $a,b$ 均为偶数或均为奇数，则令 $r$ 为 $0$。

​ 此外，如果 $a,b$ 一奇一偶，则令 $r$ 为 $1$。

2、重复第一步用商 $q$ 除以 $-1+i$ 记录下余数 $r$，直到商为 $0$，运算过程结束。

3、从下往上读取余数，就可得到 “复数整数” $a+bi$ 的 $-1+i$ 进制表示。

例如：整数 $2 = 2+ 0i$ 的运算过程：

整数 $2$ 的实部和虚部都是偶数，所以余数为 $0$ ，$\frac{2}{-1+i} =(-1-i)$ 余 $0$

$-1-i$ 的实部和虚部均为奇数，所以余数为 $0$，$\frac{-1-i}{-1+i}=i$ 余 $0$

$i$ 的实部为偶数，虚部为奇数，所以余数为 $1$，$\frac{i}{-1+i}=1$ 余 $1$

$1$ 的实部为奇数，虚部为偶数，所以余数为 $1$，$\frac{1}{-1+i}=0$ 余 $1$

商为 $0$，运算结束，从下往上读取，得到整数 $2$ 用$-1+i$进制表示为1100。

下表列出了 $-1+i$ 进制的位串0000至1111对应的十进制下的“复数整数”。

输入一个 $-1+i$ 进制下的数（为了简化，我们将0,1位串用一个十六进制整数表示），输出其对应的十进制下的“复数整数” $a+bi$。

在一行中输入一个 $-1+i$ 进制下的数（十六进制表示，使用 09 以及大写 AF）。

• 35% 的数据保证答案的 $|a|, |b| \leq 100$；
• 58% 的数据保证答案的 $|a|, |b| \leq 2~147~483~647$；
• 100% 的数据保证答案的 $|a|, |b| \leq 9~223~372~036~854~775~807$.

在一行中输出对应的十进制下的“复数整数” $a+bi$（$a,b$均为整数），省略的情况与正常书写复数时一致，请参考上面的表格以及样例。