TopCoder

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

62.5% (20/32)

Tags

Description

你有玩過人生抽獎遊戲嗎?

在這個遊戲裡玩家扮演的角色會經歷許多不同的事件,且每一個事件有一個喜悅值,依據事件不同則有不同的喜悅值
在遇到曾經經歷過的事件時,主角可能會因為經歷過而產生更多的喜悅,也可能因為經歷過太多次而感到無聊,導致喜悅值減小
具體來說,在出生後遇到第y次喜悅值為x的事件時當下開心程度是$ ( x \times y ) \mod N $小紬(Mugi)有許多詢問,每次詢問當玩家在$L$點出生,在$R$點結束回合$(L\leq R)$
玩家在這段時間內經歷的喜悅第$k$大的一天,問其喜悅值有多大?

Input Format

輸入一個數字$N$ $(1 \le N \le 10 ^ 5 )$
輸入$N$個數字$(1 \le a_i \le N)$
接著輸入一個數字$Q$ $(1 \le Q \le 10 ^ 5 )$
接著輸入$Q$行 每行包含三個數字$L,R,K$$(1 \le L \le R \le N )$, $(1 \le K \le R-L+1 )$

Output Format

輸出對於每段時間內經歷的喜悅第$k$大的一天,問其喜悅值有多大?

Sample Input

10
2 3 2 3 2 3 2 3 2 3
5
1 10 1
2 9 8
3 7 4
4 6 2
5 5 1

Sample Output

9
2
3
3
2

Hints

子任務(測資)額外限制分數
1(0~9)$N,Q \le 10 ^ 3$13
2(10~19)$N,Q \le 10 ^ 4 $36
2(20~29)51

範例測資中的第二筆詢問
區間$[2,9]$將會置換成
3 2 6 4 9 6 2 8

其中第8大的數為2

各位學弟不要像我一樣油,不然會沒有朋友喔>< By OT

Problem Source

Problem Set by rsabcmoi,polarz

Subtasks

For Testdata: 0 ~ 9, Score: 13
For Testdata: 10 ~ 19, Score: 36
For Testdata: 20 ~ 29, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536