#MX129. Dynamic Insertion

Dynamic Insertion

题目描述

给定一个非严格递增的数组 {an}\{a_n\}(下标从 11 开始),描述了这个色块序列,每次该数组会发生如下“融合”变换:

  • 若数组长度为 ll,对于每个 1≤i<l1\le i<l,在 ai,ai+1a_i,a_{i+1} 之间插入一个新数 ⌊ai+ai+12⌋\left\lfloor\dfrac{a_i+a_{i+1}}2\right\rfloor。

其中 ⌊x⌋\lfloor x\rfloor 表示对 xx 向下取整。

你需要回答 qq 组询问,每次询问第 kk 次“融合”变换后是否存在色块 xx。

输入格式

第一行两个整数 n,qn,q,表示初始数组长度和询问组数。

接下来一行 nn 个整数,表示原始的数组 aa。

接下来 qq 行,每行两个数 k,xk,x,描述每组询问。

输出格式

对于每组询问,输出仅一行一个字符串。若存在,输出 Yes;否则,输出 No(大小写敏感)。

样例 1 输入

2 2
1 10
2 3
2 4

样例 1 输出

Yes
No

样例 1 说明

对于数组 a=[1,10]a=[1,10],依次进行变换:

  • 第一次变换后,变成 [1,5‾,10][1,\underline{\textbf5},10]。

  • 第二次变换后,变成 [1,3‾,5,7‾,10][1,\underline{\textbf3},5,\underline{\textbf7},10]。

容易发现两次变换后,33 在数组中,44 不在数组中。

样例 2

见选手目录下的 juncture/juncture2.in\textit{\textbf{juncture/juncture2.in}} 与 juncture/juncture2.ans\textit{\textbf{juncture/juncture2.ans}}。

该样例与测试数据 1∼51\sim 5 满足同样的约束条件。

样例 3

见选手目录下的 juncture/juncture3.in\textit{\textbf{juncture/juncture3.in}} 与 juncture/juncture3.ans\textit{\textbf{juncture/juncture3.ans}}。

该样例与测试数据 6∼96\sim 9 满足同样的约束条件。

样例 4

见选手目录下的 juncture/juncture4.in\textit{\textbf{juncture/juncture4.in}} 与 juncture/juncture4.ans\textit{\textbf{juncture/juncture4.ans}}。

该样例与测试数据 13∼2013\sim 20 满足同样的约束条件。

数据规模与约定