#P10565. Recursive Lights Toggle

    ID: 12586 Type: Default 1000ms 256MiB

Recursive Lights Toggle

Recursive Lights Toggle

You are given a row of n lights numbered from 1 to n which are initially off. You perform a series of operations defined recursively as follows:

For each light i (from 1 to n in order), you perform the function press(i) which does the following:

[ \text{press}(x): \quad \begin{cases} \text{toggle light } x \quad (0 \to 1 \text{ or } 1 \to 0),
\text{for every } y \text{ such that } x\mid y \text{ and } x < y \le n, \text{ call } \text{press}(y). \end{cases} ]

The entire process is performed by calling press(i) for all i from 1 to n (i.e. in order, unconditionally).

For example, consider n = 4. The operations when calling press(1) are as follows:

  1. Call press(1): toggle light 1 (it becomes on). Then for every j with 1|j and 1 < j ≤ 4, call press(j) in order.
  2. When press(1) calls press(2): toggle light 2 (it becomes on) and then for every j with 2|j and 2 < j ≤ 4, call press(j). In this case, press(2) calls press(4) (toggling light 4 on).
  3. Back in the call of press(1): next press(1) calls press(3), toggling light 3 on. (No further call since 3×2=6 > 4.)
  4. Then press(1) calls press(4) directly, toggling light 4 again (so it turns off).

After the call of press(1), later the outer loop still calls press(2), press(3), and press(4) unconditionally. A careful simulation of the recursive calls shows that every light with index greater than 1 is toggled an even number of times, while light 1 is toggled exactly once. Hence, after all operations:

  • Light 1 is on (since it is toggled once).
  • Every light from 2 to n is off (since they are toggled an even number of times).

Your task is: Given two integers n and k, determine whether light k is on or off after performing all the operations.

inputFormat

The input consists of a single line containing two space‐separated integers n and k (1 ≤ kn ≤ 109).

outputFormat

Output a single line: ON if the k-th light is on after all operations, and OFF otherwise.

Note: Based on the process described, a complete simulation shows that the first light is toggled an odd number of times (and hence is on), while every other light is toggled an even number of times (and hence remains off). Therefore, the answer is ON if and only if k = 1.

sample

1 1
ON