Powers of Three Walk

Interview

Time limit2sMemory limit512 MB

Summary

Given a target point, decide whether it is reachable if stage k moves exactly 3^k in one of the four axis directions.

Level: Medium5 of 10
Topics: Math, Number theory, Bit manipulation
Solved: No attempts yet

Problem

Donghyeok stands at the origin $(0, 0)$ of a plane of infinite size.

He moves in numbered stages and wants to arrive at the point $(x, y)$ . Stage numbers start at $0$ and grow by $1$ .

At stage $k$ he picks one of four directions, right ( $x$ increases), left ( $x$ decreases), up ( $y$ increases), or down ( $y$ decreases), and then moves exactly $3^k$ in that direction. He cannot skip a stage.

He performs as many stages as he wants and then stops. Stopping at the origin without performing a single stage is allowed.

Given $x$ and $y$ , write a program that decides whether $(x, y)$ can be reached from $(0, 0)$ .

Input

The first line contains two integers $x$ and $y$ separated by a space. ( $-10^9 \le x, y \le 10^9$ )

Output

Print $1$ if $(x, y)$ can be reached from $(0, 0)$ , and $0$ otherwise.

If $x$ and $y$ are both $0$ , he is already there before any stage, so print $1$ .

Examples5

Example 1
Input
```
1 3
```
Expected output
```
1
```
Example 2
Input
```
0 2
```
Expected output
```
1
```
Example 3
Input
```
1 9
```
Expected output
```
0
```
Example 4
Input
```
3 0
```
Expected output
```
0
```
Example 5
Input
```
1 1
```
Expected output
```
0
```