题目背景

小 P 和小 O 玩取石子游戏。

题目描述

桌子上有两堆石子 $A,B$，其中 $A$ 初始有 $k$ 个石子，$B$ 初始没有石子。

小 P 和小 O 轮流将石子从 $A$ 单向移走至 $B$，小 P 先移动，当某一方无法移动时就输了。

显然，小 P 只要在第一步把石子全部移走就赢了。因此，小 O 加了一个限制：当 $B$ 有 $i$ 个石子时，一次操作只能移动 $x$ 个石子，其中 $x\in S_i$。当然，$S_i=\varnothing$ 也是一种无法移动。

注意，即使 $x$ 比 $A$ 当前的石子数目 $k$ 多，也不能移走 $x$ 个石子，或是在 $k\not\in S_i$ 的情况下移走 $k$ 个石子。

给定集合序列 $\{S_n\}$，小 P 想知道，如果双方都采用最优策略，哪一方会赢。

但这个问题太简单了，于是小 P 想对 $k=0,\cdots,n$ 都计算出答案。

输入格式

第一行一个整数 $n$，含义如上。

为了防止输入数据过大，采用如下方式输入 $\{S_n\}$：
接下来 $n$ 行，其中第 $i$ 行包含一个正整数 $x$。当且仅当 $x$ 的二进制表示从低到高第 $j$ 位为 $1$ 时，$j\in S_{i-1}$。

输出格式

共 $n+1$ 行，每行为 P 或 O，表示获胜方。

2
1
0

O
P
P

8
213
423
132
234
432
121
123
231

O
P
O
P
P
P
P
P
P

样例解释

样例 1 中：

$S_0=\{1\},S_1=\varnothing$。

除了 $k=0$ 时无法移动，小 P 只需要移动 $1$ 个石子就赢了。

数据范围

对于 $100\%$ 的数据，$0\le x <2^{10}$，$1\le n\le 5\times 10^5$。

• 子任务 1（30 分）
  • $n\le 1000$。
• 子任务 2（30 分）
  • $n\le 10^5$。
• 子任务 3（40 分）
  • 没有特殊限制