[Solution] Tonya and Burenka-179 solution codeforces

Tonya and Burenka-179 solution codeforces – Tonya was given an array of 𝑎a of length 𝑛n written on a postcard for his birthday. For some reason, the postcard turned out to be a cyclic array, so the index of the element located strictly to the right of the 𝑛n-th is 11. Tonya wanted to study it better, so he bought a robot “Burenka-179”.

Table of Contents

Tonya and Burenka-179 solution codeforces

A program for Burenka is a pair of numbers (𝑠,𝑘)(s,k), where 1𝑠𝑛1≤s≤n1𝑘𝑛11≤k≤n−1. Note that 𝑘k cannot be equal to 𝑛n. Initially, Tonya puts the robot in the position of the array 𝑠s. After that, Burenka makes exactly 𝑛n steps through the array. If at the beginning of a step Burenka stands in the position 𝑖i, then the following happens:

  1. The number 𝑎𝑖ai is added to the usefulness of the program.
  2. “Burenka” moves 𝑘k positions to the right (𝑖:=𝑖+𝑘i:=i+k is executed, if 𝑖i becomes greater than 𝑛n, then 𝑖:=𝑖𝑛i:=i−n).

Help Tonya find the maximum possible usefulness of a program for “Burenka” if the initial usefulness of any program is 00.

Also, Tony’s friend Ilyusha asks him to change the array 𝑞q times. Each time he wants to assign 𝑎𝑝:=𝑥ap:=x for a given index 𝑝p and a value 𝑥x. You need to find the maximum possible usefulness of the program after each of these changes.

Tonya and Burenka-179 solution codeforces

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) is the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑞q (2𝑛21052≤n≤2⋅1050𝑞21050≤q≤2⋅105).

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — elements of the array.

The following 𝑞q lines contain changes, each of them contains two integers 𝑝p and 𝑥x (1𝑝𝑛1≤p≤n1𝑥1091≤x≤109), meaning you should assign 𝑎𝑝:=𝑥ap:=x.

It is guaranteed that the sum of 𝑛n and the sum of 𝑞q over all test cases do not exceed 21052⋅105.

Output

For each test case, output 𝑞+1q+1 numbers — the maximum usefulness of a program initially and after each of the changes.

Tonya and Burenka-179 solution codeforces

Example
input

Copy
4
2 1
1 2
1 3
4 4
4 1 3 2
2 6
4 6
1 1
3 11
9 3
1 7 9 4 5 2 3 6 8
3 1
2 1
9 1
6 3
1 1 1 1 1 1
1 5
4 4
3 8
output

Copy
3
5
14
16
24
24
24
57
54
36
36
6
18
27
28

Tonya and Burenka-179 solution codeforces

In the first test case, initially and after each request, the answer is achieved at 𝑠=1s=1𝑘=1k=1 or 𝑠=2s=2𝑘=1k=1.

In the second test case, initially, the answer is achieved when 𝑠=1s=1𝑘=2k=2 or 𝑠=3s=3𝑘=2k=2. After the first request, the answer is achieved at 𝑠=2s=2𝑘=2k=2 or 𝑠=4s=4𝑘=2k=2.

For Solution

“Click Here”

Leave a Comment