Bajtocy 教授正在进行外星 DNA 实验。他发现它会发生重复突变——每个突变都以相同的方式发生:外来 DNA 的一些连续子序列变得活跃,自我复制,副本被破坏并将自身插入到原始子序列之后。激活的连续子序列的损坏副本是通过首先连接该子序列中偶数位置处的所有元素,然后连接末尾奇数位置处的所有元素来形成的。也就是说,如果激活的子序列由 11 个元素组成并表示为 s1s2...s11,则其损坏的副本为 s2s4s6s8s10s1s3s5s7s9s11。
例如,如果原始序列为“ACTGG”,突变发生在片段[2, 4]上(即激活的子序列为“CTG”),则突变后的DNA为:“ACTGTCGG”。激活子序列的损坏副本用粗体标记。
Bajtocy 教授写下了原始 DNA 序列和依次发生的突变,现在他要求你恢复所有突变后 DNA 序列的前 k 个元素。
输入
输入的第一行包含原始DNA序列,仅由字母“A”、“C”、“T”和“G”组成,长度不超过3·106。
第二行包含一个整数 k (1 ≤ k ≤ 3·106)。
第三行包含一个整数 n (0 ≤ n ≤ 5000) — 突变数。接下来的 n 行按时间顺序描述突变 - 每个突变由两个数字 li 和 ri (1 ≤ li ≤ ri ≤ 109) 描述,这意味着连续子序列 [li, ri] 已变得活跃并克隆自身,将自身与损坏的副本连接起来。
保证输入数据正确,即没有突变作用于DNA序列中不存在的元素,并且得到的DNA序列至少有k个元素。
假设 DNA 元素从 1 开始索引,符号 [l, r] 表示 DNA 序列的连续子序列,由 r - l + 1 个元素组成,从第 l 个 DNA 序列元素开始,到第 r 个 DNA 序列元素结束。
输出
输出一行,包含突变 DNA 序列的前 k 个字母。
示例
输入 #1
GAGA 4 0
输出 #1
GAGA
输入 #2
ACGTACGT 16 2 1 2 2 8
输出 #2
ACCAGTACCGACATCG
注意
在第二个示例中,第一次突变后的序列是“ACCAGTACGT”。第二次突变后是“ACCAGTACCGACATCGT”。