TopCoder

Thumb mikasa mikoto furikae
Omelet
Mikoto Saikou!

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

20.0% (4/20)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、兩歲又四個月時開始研究「匹配問題」、三歲時開始研究蝴蝶、六歲時開始發大財,而現在要講的,是殿壬三歲又六個月大時的故事。

殿壬在三歲又六個月大時,開始迷上各種序列問題,例如:區間加值、區間絕對眾數、區間最大值$......$等等經典問題。而他今天,他遇到了一到序列問題,他想請你幫幫他,解決這個問題。

給你一個長度為 $N$ 的整數序列 $a_1, a_2, a_3, \cdots \cdots , a_N$ ,並且依序執行 $Q$ 個操作,每個操作不外乎是下面幾種:

  • $1 \ x \ y$ :把 $a_x$ 設成 $y$ 。
  • $2 \ L \ R \ k$ :對於每個 $i \in [L, R]$ ,讓 $a_i = \lfloor \frac{a_i}{k} \rfloor$ 。其中 $\lfloor x \rfloor$ 代表小於等於 $x$ 的最大整數。
  • $3 \ L \ R$ :請輸出 $a_L, a_{L+1}, a_{L+2}, ......, a_{R-1}, a_{R}$ 的絕對眾數,如果絕對眾數不存在,請輸出 -1 。一個數字若為 $T$ 個數字的絕對眾數,代表這個數字至少在 $T$ 個數字中出現 $\lfloor \frac{T+2}{2} \rfloor$ 次。

Input Format

輸入的第一行包含兩個正整數 $N, Q$ ,代表序列的長度,以及操作的個數。

接下來的一行,包含 $N$ 個整數,第 $i$ 個整數為 $a_i$ 。

接下來的 $Q$ 行,每行 依序 代表操作,操作的格式如題目敘述所述。

  • $1 \le N, Q \le 10^ 5$
  • $1 \le L \le R \le N$
  • $1 \le x \le N$
  • $0 \le a_i, y \le 10^ 9$
  • $1 \le k \le 10^ 9$

Output Format

對於操作三,請輸出相對應的數字。

Sample Input

5 10
6 7 6 7 6
3 1 4
3 3 5
2 2 3 2
3 1 3
3 1 4
1 4 3
3 1 5
2 1 5 100
1 1 1
3 1 2

Sample Output

-1
6
3
-1
3
-1

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~10 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 6000 524288 262144 1
1 6000 524288 262144 1
2 6000 524288 262144 1
3 6000 524288 262144 1
4 6000 524288 262144 1
5 6000 524288 262144 1
6 6000 524288 262144 1
7 6000 524288 262144 1
8 6000 524288 262144 1
9 6000 524288 262144 1
10 6000 524288 262144 1