YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙
时间限制：3000MS 内存限制：131072KB
难度：6.0
-
题目描述
已知密匙与一个长度为 n 的字符串有关，字符串中的字符都来自于字符集 \{\text{‘a’..}\text{‘z’}, \text{‘?’}\}，每个 \text{‘?’} 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：
在输入的 m 次操作后与这个串操作之前的样子相比没有改变。
一次操作是翻转这个串的第 l_i 个字符到第 r_i 个字符。
求出字典序第 K 小的合法的能被填出的串，因为密码就是它。
-
输入格式
第一行三个数 n,m,k 。
第二行一个长度为 n 的串。
接下来 m 行每行两个数 l_i 和 r_i 。
-
输出格式
一个串，表示字典序第 K 小的合法的能被填出的串。
-
样例输入
-
样例输出
-
数据规模与约定
对于 100\% 的数据，保证 n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18} 。