CF217E.Alien DNA

Professor Bajtocy is conducting experiments on alien DNA. He has discovered that it is subject to repetitive mutations — each mutation happens in the same way: some continuous subsequence of the alien DNA becomes active, copies itself, the copy gets mangled and inserts itself right after the original subsequence. The mangled copy of the activated continuous subsequence is formed by first joining all the elements at the even positions in that subsequence, and then joining all the elements at the odd ones at the end. That is, if the activated subsequence consists of 11 elements and represented as _s_1_s_2... _s_11, its mangled copy is _s_2_s_4_s_6_s_8_s_10_s_1_s_3_s_5_s_7_s_9_s_11.

For example, if the original sequence was "ACTGG" and the mutation happened on the segment [2, 4] (that is the activated subsequence is "CTG"), the mutated DNA is: "ACTGTCGG". The mangled copy of the activated subsequence is marked with bold font.

Professor Bajtocy has written down the original DNA sequence and the mutations that sequentially happened to it, and he now asks you to recover the first k elements of the DNA sequence after all the mutations.

巴伊托西教授正在对外星DNA进行实验。他发现外星DNA会经历重复的突变——每次突变都以相同的方式发生：DNA某一段连续子序列被激活，该子序列自我复制，其副本经过“扭曲”后插入到原序列之后（紧邻原激活子序列末尾）。所谓“扭曲”副本，是指先将该激活子序列中所有偶数位置上的元素依次连接起来，再将所有奇数位置上的元素依次连接在后面。即，若激活子序列由11个元素组成，记为 $s_1s_2\ldots s_{11}$，则其扭曲副本为 $s_2s_4s_6s_8s_{10}s_1s_3s_5s_7s_9s_{11}$。

例如，若原始序列为 "ACTGG"，且突变发生在区间 $[2,\,4]$（即激活子序列为 "CTG"），则突变后的DNA序列为 "ACTGTCGG"。其中扭曲副本部分以粗体标出。

巴伊托西教授已记录下原始DNA序列以及按顺序发生的全部突变操作，现请你求出所有突变完成后DNA序列的前 $k$ 个元素。

The first line of input contains the original DNA sequence, consisting only of letters "A", "C", "T" and "G" and not exceeding 3·106 in length.

The second line contains a single integer k (1 ≤ k ≤ 3·106).

The third line contains a single integer n (0 ≤ n ≤ 5000) — the number of mutations. The next n lines describe the mutations in chronological order — each mutation is described by two numbers l__i and r__i (1 ≤ l__i ≤ r__i ≤ 109), meaning that the continuous subsequence [l__i, r__i] has become active and cloned itself, joining itself with the mangled copy.

It is guaranteed that the input data is correct, that is, no mutation acts on non-existing elements of the DNA sequence, and the resulting DNA sequence has at least k elements.

Assume that the DNA elements are indexed starting from 1 and that the notation [l, r] meaning the continuous subsequence of DNA sequence that consists of r - l + 1 elements starting at the l-th DNA sequence element and ending at the r-th DNA sequence element.

输入的第一行包含原始 DNA 序列，该序列仅由字母 “A”、“C”、“T” 和 “G” 组成，长度不超过 $3\cdot10^6$。

第二行包含一个整数 $k$（$1\le k\le 3\cdot10^6$）。

第三行包含一个整数 $n$（$0\le n\le 5000$）——表示突变次数。接下来的 $n$ 行按时间顺序描述各次突变——每次突变由两个数 $l_i$ 和 $r_i$（$1\le l_i\le r_i\le 10^9$）描述，表示连续子序列 $[l_i,\,r_i]$ 变为活跃状态并自我复制，将自身与被破坏的副本拼接在一起。

保证输入数据合法，即：任何一次突变均不作用于 DNA 序列中不存在的元素，且最终得到的 DNA 序列长度至少为 $k$。

假设 DNA 元素的下标从 1 开始；记号 $[l,\,r]$ 表示 DNA 序列的一个连续子序列，该子序列包含 $r-l+1$ 个元素，起始于第 $l$ 个 DNA 序列元素，终止于第 $r$ 个 DNA 序列元素。

Output a single line, containing the first k letters of the mutated DNA sequence.

输出一行，包含突变后 DNA 序列的前 k 个字母。

In the second example, after the first mutation the sequence is "ACCAGTACGT". After the second mutation it's "ACCAGTACCGACATCGT".

在第二个例子中，第一次突变后，序列为“ACCAGTACGT”。第二次突变后，序列为“ACCAGTACCGACATCGT”。