#557. 「Antileaf's Round」你这衣服租来的吗

内存限制:512 MiB 时间限制:1200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AntiLeaf

题目描述

衣服

给你一个长为 n 的序列,然后对序列进行 m 次操作,操作有两种:

  • M l r v:把区间 [l,r] 的所有数都改成 v
  • Q l r k v:询问区间 [l,r] 中从左到右第 k v 的下标(下标从 1 开始),不存在则输出 0
    为了防止你采用离线算法,本题强制在线,每次输入的所有整数都需要异或上次询问的答案(如果还没有进行过询问则为 0 ),得到的才是真正的输入。

输入格式

第一行两个非负整数,分别表示 n,m
第二行 n 个正整数,表示原来的序列。
以下 m 行,每行描述一个操作,格式如上所述。

输出格式

对于每个 Q 操作,单独一行输出一个整数表示答案。

样例

样例输入

5 5
2 3 3 3 3
Q 2 4 3 3
M 7 0 2
Q 0 1 5 2
M 5 5 7
Q 7 1 6 7

样例输出

4
4
0

样例解释

原本的输入应该是

5 5
2 3 3 3 3
Q 2 4 3 3
M 3 4 6
Q 4 5 1 6
M 1 1 3
Q 3 5 2 3

数据范围与提示

n,m\le 10^5 ,保证任何时刻均有 0\le a_i\le 10^9