在编程之地,有几条被称为“哲学家漫步”(Philosopher’s Walk)的路径,供哲学家们休憩。哲学家漫步是一条位于正方形区域内的路径,区域内绿意盎然。这些树林有助于哲学家思考,但他们种得太密,以至于哲学家在树林中迷了路。
幸运的是,所有哲学家漫步的结构都很相似;哲学家漫步的结构是根据 $2^k$ 米边长的正方形区域内的相同规则设计和建造的。设计该路径的规则是:当 $k=1$ 时,每走 1 米后向右转 90 度;对于大于 1 的整数 $k$,则以分形方式由 4 个子路径构成。图 F.1 展示了 $k$ 分别为 1、2 和 3 时的三条哲学家漫步路径。哲学家漫步 $W_2$ 由 4 个 $W_1$ 结构组成,其中左下角和右下角的结构分别顺时针和逆时针旋转了 90 度;上方的结构与 $W_1$ 具有相同的结构。对于任何大于 1 的整数 $k$,其对应的 $W_k$ 也是如此。这一规则由数学家大卫·希尔伯特(David Hilbert,1862–1943)提出,由此产生的路径通常以他的名字命名为希尔伯特曲线(HILBERT CURVE)。他曾谈到使用这种曲线填充 $2^k$ 边长的正方形的空间填充方法,每一条哲学家漫步路径都是根据这种方法设计的。
图 F.1:大小分别为 $2^1=2$,$2^2=4$ 和 $2^3=8$ 的三条哲学家漫步路径。
泰川(Tae-Cheon)负责营救在哲学家漫步路径中迷路的哲学家,他使用热气球进行搜救。幸运的是,每位迷路的哲学家都可以向泰川报告他所走的米数,泰川知道哲学家漫步路径的边长。他必须确定迷路哲学家的位置,即假设哲学家漫步路径放置在笛卡尔平面的第一象限,且每个单位长度为一个方格,求出其 $(x, y)$ 坐标。假设左下角方格的坐标为 $(1, 1)$。哲学家漫步的入口始终在 $(1, 1)$,出口始终在 $(n, 1)$,其中 $n$ 是边长。同时假设哲学家在入口处时已经走了一米,并且他总是向前走向出口,不会后退。
例如,如果迷路哲学家在图 F.1(b) 所示的 $W_2$ 路径中走的米数为 10,则你的程序应报告 $(3, 4)$。
你的任务是编写一个程序,帮助泰川根据迷路哲学家所走的米数和哲学家漫步路径的边长,报告该哲学家的位置。快点!哲学家急需你的帮助。
输入格式
程序从标准输入读取数据。输入包含一行,包含两个正整数 $n$ 和 $m$,分别表示哲学家漫步路径的边长和迷路哲学家所走的米数,其中 $n = 2^k$,且 $m \le 2^{2k}$,其中 $k$ 为满足 $0 < k \le 15$ 的整数。
输出格式
程序将结果写入标准输出。输出应包含两个整数 $x$ 和 $y$,中间用空格分隔,其中 $(x, y)$ 是该哲学家在给定哲学家漫步路径中的位置。
样例
样例输入 1
4 10
样例输出 1
3 4
样例输入 2
8 19
样例输出 2
2 6