#1069. Luke's Card

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: TosakaUCW

题目描述

在宇宙的深处,宇宙大帝 Luke 正在操控一座名为 "无限之塔" 的神秘装置。这个装置能够通过不断叠加和复制生成复杂的卡组,只有掌握至高智慧的人才能完全控制它。

在这个装置中,Luke 面对的是一个空的卡组。他需要通过两种独特的操作来构建这个卡组:

  1. 能量注入:Luke 可以将一个特定的能量卡牌(表示为整数 )注入到序列的末尾。
  2. 超级风怒:Luke 可以将他已经构建好的卡组重复注入更多次。具体来说,他可以选择将当前卡组复制 次,并追加到现有卡组的末尾。

每次操作都会使卡组变得越来越庞大与复杂,充满了难以预测的变化。宇宙中许多玩家都在等待操作这些神秘的卡组,他们迫不及待想知道某个特定位置上的卡牌是什么。

为了回应这些探险者的请求,Luke 决定解答他们的问题。他接到了 个查询,每个查询希望知道生成后的卡组中某个具体位置上的数据值。作为 Luke 最信任的助手,你需要帮助他解答这些问题。

输入格式

第一行包含两个整数 (),分别表示操作的总数和查询的总数。

接下来有 行,每行两个整数 () 和 ()

接下来有 个整数 (),表示探险者想知道卡组中的第 个卡牌,其中 是完成所有 操作后的卡组大小。

输出格式

对于每个查询,输出卡组中对应位置的卡牌。

样例

Input

2 2
1 1
1 2
1 2

Output

1 2