#510. 「LibreOJ NOI Round #1」北校门外的回忆

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

题目描述

回到了正常的时空,神犇和 LCR 暂时过着安宁又平静的生活,他们回想起三年前的往事……

秋日的北校门格外美丽,这天,神犇和 LCR 第一次因化学中二而相遇……

令神犇难以忘怀的是,他与 LCR 相遇是在校门外的树下。那棵树的奇特形态深深印在神犇的脑中。神犇称这棵树是一棵“K 项树”。
为了纪念他和 LCR 的第一次相遇,神犇后来写的树状数组都是以 K 进制而非二进制为基的。

神犇的机房里有一位名叫 LCA 的蒟蒻,一天他碰巧欣赏到了神犇的代码,它发现神犇的树状数组是这么写的:

function add(x,v)
    while x <= n do
        s[x] = s[x] xor v
        x = x + lowbitv(x)
    end while
end function

function query(x)
    ans = 0
    while x > 0 do
        ans = ans xor s[x]
        x = x - lowbit(x)
    end while
    return ans
end function

其中:

  • lowbit(x)\mathrm{lowbit}(x)lowbit(x) 表示 KKK 进制下 xxx 的最低非零位的值(例如当 K=5K=5K=5 时,lowbit(230(5))=30(5)=15(10)\mathrm{lowbit}(230_{(5)})=30_{(5)}=15_{(10)}lowbit(230(5))=30(5)=15(10)
  • lowbitv(x)\mathrm{lowbitv}(x)lowbitv(x) 表示 KKK 进制下 xxx 的最低非零位的位值(即该位为 1 其它位都为 0 时的数值,例如当 K=5K=5K=5 时,lowbitv(230(5))=10(5)=5(10)\mathrm{lowbitv}(230_{(5)})=10_{(5)}=5_{(10)}lowbitv(230(5))=10(5)=5(10)

这份代码的作用是维护一个长度为 nnn 的序列 AAA,支持单点异或上一个值和求前缀异或和s[i]s[i]s[i] 维护的是 i(s[i]lowbit(s[i]),s[i]]Ai。(⊕\oplus 表示按位异或)

LCA 觉得这种写法十分不错,于是自己也这么写,但总是写挂的 LCA 漏打了一个字符,还把 KKK 的值设定得大了很多。

也就是说,LCA 的代码是这么写的:

function add(x,v)
    while x <= n do
        s[x] = s[x] xor v
        x = x + lowbit(x) //注意,这里是 lowbit,这也是两份代码唯一的区别
    end while
end function

function query(x)
    ans = 0
    while x > 0 do
        ans = ans xor s[x]
        x = x - lowbit(x)
    end while
    return ans
end function

注意:两个函数调用的都是 lowbit\mathrm{lowbit}lowbit

紧接着 LCA 就发现自己的代码跑得比谁都慢,他百思不得其解,只好来请你帮他解决这个问题。

请写一个和 LCA 的程序的输出相同的程序。

注意,你的任务是写一个和 LCA 的程序输出相同的程序,而不是正确的程序。

输入格式

第一行三个正整数 n,q,Kn,q,Kn,q,K,表示序列长度,操作数和进制的基数。序列初始全为 0,LCA 的 s 数组也会初始化为全 0
接下来 qqq 行每行格式是下列之一:

  • 1 x vAxA_xAx 的值异或上 vvv。LCA 会调用 add(x,v)\mathrm{add}(x,v)add(x,v)
  • 2 x 查询 i(0,x]Ai。LCA 会输出一行一个整数,为调用 query(x)\mathrm{query}(x)query(x) 的结果。

输出格式

对于每个 2 操作,输出一个整数表示 LCA 程序的输出

注意,你的任务是写一个和 LCA 的程序输出相同的程序,而不是正确的程序。

样例

样例输入

7 16 5
1 1 10
2 1
1 4 15
2 4
1 6 10
1 4 15
2 6
2 6
1 6 5
1 5 12
2 3
1 2 5
1 4 5
2 5
1 6 0
1 5 5

样例输出

10
5
10
10
0
12

更多样例

见附加文件或备用网盘链接(提取码:q5bs

数据范围与提示

对于 100%100\%100% 的数据,1≤x≤n≤109,1≤q≤2×105,2≤K≤2×105,0≤v≤1091\leq x\leq n\leq 10^9,1\leq q\leq 2\times 10^5,2\leq K\leq 2\times 10^5,0\leq v\leq 10^91xn109,1q2×105,2K2×105,0v109

注意,你的任务是写一个和 LCA 的程序输出相同的程序,而不是正确的程序。

Subtask # 分值 n,qn,qn,q 的限制 KKK 的限制
1 171717 1≤n,q≤30001 \leq n, q \leq 3000 1n,q3000 2≤K≤30002 \leq K \leq 3000 2K3000
2 151515 1≤n≤2×1051 \leq n \leq 2\times 10^51n2×105 K=2K=2 K=2
3 191919 KKK 是奇数
4 242424
5 252525