题目大意
给定一个字符串 $S$，执行 $10^{100}$ 次以下操作：
- 首先，令字符串 $T$ 为字符串 $S$ 中所有大写字母变为小写字母，小写字母变为大写字母的结果。
- 其次，将 $T$ 拼接在 $S$ 后面。
接下来，有一些询问：
- 请输出在所有操作执行完成之后 $S$ 的第 $K$ 个字母。
思路
乍一看，好大的数据范围！这题真难！
仔细思考一番发现，我们可以令原始的 $S$ 为一号串，刚开始$T$ 为二号串，然后每一次操作完的字符串就是一号串和二号串的组合。
于是，这题是……找规律？
以下内容为考场上研究的内容：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1
1 2 3 4
1 2 2 1
解释一下，这堆东西每两行为一组，每组中第一行为位置，第二行为编号（一或二）。第一组是刚才说的一号二号串的组合，第二组就是把第一组中的 1 2 2 1 看作一号串，2 1 1 2 看作二号串，第三组同理。
规律的话嘛，就是可以发现每一层的规律都一样，最后一层就是 1 2 2 1。当然不能直接计算出来了，不过可以递归。单次查询的时间复杂度不高，递归调用的时间复杂度较为合理。$dfs(x)$ 的时间复杂度为 $O(log_4x)$，可以解决本题。