Your Lie in April

Z2625 Time Limit: 1.000 s Memory Limit: 64 MB
Submit Submissions

In the anime 《Your Lie in April》《四月は君の嘘》, the male protagonist, Kousei Arima is a famous 14 year old pianist who won several championships in piano competitions, and even got the title, The Human Metronome.

Kousei would be perfoming his final piano recital. The piece consists of $N$ movements ($1 \le N \le 10^5$). Since Kousei was practicing so hard, he looped the $N$ movements periodically everytime, until he practiced $K$ of them ($1 \le K \le 10^{18}$). In simpler terms, the song will be practied in the following sequence: $1^{st}$ movement -> $2^{nd}$ movement -> ... -> $N^{th}$ movement -> $1^{st}$ movement -> ... -> $(K \mod N + 1)^{th}$ movement.

However after his mother, Saki, died suddenly, Kousei became so emotional during his practices. Originally, the duration for playing the $i^{th}$ movement is $H_i$ hours $(1\le H_i \le 23)$. Now, he has a different pace playing the piece. So, Kousei decided to make an adjustment each time after practicing once. He'll practice the piece a total of $Q$ times. After practing the $i^{th}$ time, Kousei changes the duration of movement $X_i$ into a new one. Formally, he sets the value of $H_{X_i}$ to $A_i$, $(1\le A_i \le 23)$.

As a passionate pianist, Kousei is so focused on his performance that he doesn’t know the current time. Kousei starts each of his practices at the 00:00 someday. After every adjusment, can you find out what will be the hour shown on the clock be after he practiced the adjusted piece next time. You are not required to find out which day or minute is it, just the hour. Assume that there's exactly 24 hours every day, and the possible answers are only 0 to 23.

Input

The first line contains 3 integers, $N$, $Q$ and $K$.
The second line contains $N$ integers, $H_1, H_2 ... H_N$.
Each of the following $Q$ lines contains of 2 integers, where the $i^{th}$ line contains $X_i$ and $A_i$.

Output

Output $Q$ lines, where the $i^{th}$ line represents the answer after the $i^{th}$ adjustment.

Subtasks

For all cases,
$1 \le N,Q \le 10^5$
$1 \le K \le 10^{18}$
$1 \le H_i \le 23$ for all $1 \le i \le N$
$1 \le A_i \le 23$ and $1 \le X_i \le N$ for all $1 \le i \le Q$

Subtask 1 (20 pts): $1\le K \le N \le 5$ and $1\le H_i, A_i \le 3$
Subtask 2 (35 pts): $1\le K \le N$ and $1 \le N,Q \le 1000$
Subtask 3 (22 pts): $1\le K \le 10^9$
Subtask 4 (23 pts): No additional constraints

Sample Test Cases

Input Output
4 2 3
1 2 1 3
2 1
1 3		 3
5

This test satisfies the constraints of all four subtasks.

After the first adjustment, the time required for each movement will be $[1, 1, 1, 3]$.
After playing $K = 3$ movements, the total number hours practiced will be $1+1+1 = 3$.
Hence the the hour shown on the clock be after he practiced the adjusted version will be 3.

After the second adjustment, the time required for each movement will be $[3, 1, 1, 3]$.
After playing $K = 3$ movements, the total number hours practiced will be $3+1+1 = 5$.
Hence the the hour shown on the clock be after he practiced the adjusted version will be 5.

4 2 5
5 6 7 9
1 7
1 1		 12
0

This test case satisfies the constraints of subtasks 3 and 4.

After the first adjustment, the time required for each movement will be $[7, 6, 7, 9]$.
After playing $K = 5$ movements, the total number hours practiced will be $7+6+7+9+7 = 36$.
Hence the the hour shown on the clock be after he practiced the adjusted version will be 12.

After the second adjustment, the time required for each movement will be $[1,6,7,9]$.
After playing $K = 5$ movements, the total number hours practiced will be $1+6+7+9+1= 5$.
Hence the the hour shown on the clock be after he practiced the adjusted version will be 0.

Click to copy.
Scoring: Per Subtask
Authored by wy23918, wy24215 and wy24084
Appeared in WYHK 2026 Mini Contest 2