TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

50.0% (3/6)

Tags

Description

姬桂是一個可愛的女子高中生, 就讀於賽趿馬女子高中, 夢想是出道成為世界第一的賽馬偶像, 最近的煩惱是長不高 QwQ。

粥滑名泊(簡稱粥泊)是一家在賽趿馬女子高中附近的世界知名百年粥品老店, 姬桂最喜歡吃粥泊販售的又濃又稠的綿滑白粥。 有天姬桂得知粥泊的老闆周伯要舉辦為期四個月的夏令營, 參加的人天天都可以吃粥, 興奮的姬桂立馬報名,並幸運的抽到了參加機會。 參加粥泊夏令營的粥泊粉絲,因為滿腦子都是綿滑白粥,被稱之為滑腦。 在夏令營裡,姬桂跟滑腦夥伴們天天開心的吃著粥,唱著歌,練習慢跑跟研究美化環境的技巧,生活好不充實。

每個滑腦會被分到一個班級(簡稱班),總共有 N 個班,編號 1N,每個班會有一個粥泊的工作人員,稱為班長,第 j 個班一開始有 aj 個滑腦。 夏令營裡有 Q 個事件會依序發生,分別是集合還有靈異事件。

i 個事件是集合時,周伯會要求編號在 liri 間的班全部出來排隊。 一個班在排隊時,假設班上的滑腦數是 z,那個班的班長會決定一個不超過 z 的正整數 y, 每 y 個滑腦為一列,排成一個矩形。因為 z 不見得是 y 的倍數,所以會有不超過 y1 個滑腦剩下來。

周伯覺得一個班排隊的美觀程度是: 如果班上的滑腦數是 0,因為找不到合法的 y,所以美觀程度是 1。 否則,美觀程度是排隊時剩餘的滑腦數,也就是 z 除以 y 的餘數。 周伯想知道出來集合的班級排隊美觀程度的和的最大值,以下稱這個值為好值。

i 個事件是靈異事件時,因為粥泊是百年老店,難免鬧鬼,周伯上知天文,下知地理,所以能算出鬼的奇異能量,一個非負整數 wi,以及鬧鬼範圍 [li,ri],所以一個編號在 liri 間的班, 如果本來滑腦數是 z,鬧鬼之後的滑腦數會變成本來滑腦數跟奇異能量做異或運算之後的數字,也就是 z xor wi

姬桂想引起周伯的注意,於是毛遂自薦要幫周伯算每次集合的好值,但姬桂只是很可愛而已,既不會算術也不會寫程式,請聰明的你幫幫他 >_<。

Input Format

第一行有兩個數字 N,Q,代表班級的數量跟發生的事件數。

第二行有 N 個數字 a1,a2,,aNaj 代表第 j 個班一開始的滑腦數。

接下來有 Q 行,第 i 行代表第 i 個事件:

  • 1liri 代表一個集合事件。
  • 2liriwi 代表一個靈異事件。

測資滿足:

  • 輸入的所有數字都是整數
  • 1N,Q105
  • 0aj,wi<231
  • 1liriN

Output Format

對於每個集合事件,請輸出一行為該次集合的好值。

Sample Input 1

6 5
8 8 0 3 0 1
1 1 1
1 3 3
1 4 4
1 6 6
1 1 6

Sample Output 1

3
-1
1
0
5

Sample Input 2

7 5
1 3 1 4 1 2 7
1 1 4
1 2 7
2 2 4 15
1 1 4
1 2 7

Sample Output 2

2
5
16
19

Hints

YP 是毒瘤

Problem Source

IOICamp 2020 Day5 pI

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 1 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2