题目描述

在本题中，我们按以下方式定义满二叉树和完全二叉树。

满二叉树：一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树是满二叉树，一个$n$层的满二叉树有$2^n-1$个节点。

完全二叉树：如果对满二叉树的节点，按照从上到下，从左到右的顺序，从$1$开始对节点编号，则一个$n$个节点的完全二叉树，每一个节点$i$，会和其对应编号的节点在满二叉树中的位置相同。

小码哥有一棵$n$个节点，按以上方式编号的完全二叉树。他会给出$q$个询问。 询问一：询问节点$i$的父节点编号。 询问二：询问节点$i$的左儿子节点编号。 询问三：询问节点$i$的右儿子节点编号。

如果节点$i$不存在于该树中，输出"Error"；如果节点$i$的父节点或子节点（询问的对应节点）不存在，输出"QAQ"（均不含引号）；如果询问合法，则输出询问对应的节点编号。

输入格式

第一行输入两个整数$n,q$。 接下来$q$行，每行输入两个整数$opt,i$，$i$表示询问的节点。若$opt=1$，表示询问一；$opt=2$，表示询问二；$opt=3$，表示询问三。

输出格式

输出共$q$行，对于每个询问输出你的答案。

样例输入 #1

5 5
1 10
1 2
2 2
3 2
1 1

样例输出 #1

Error
1
4
5
QAQ

说明/提示

对于40%的数据，有$1\leq n\leq 10^5$。 对于100%的数据，有$1\leq n\leq 10^{18},1\leq q\leq 10^5,1\leq i\leq 2\times 10^{18}$。