Ouroboros

1s 11 MB
Exclusive Easy+ 2.5 MathAlgorithms
ouroboros
You are given a cyclic array AA of size NN and an integer step size KK.

Transform the array such that every element AiA_i becomes the sum of its original value and the value of the element KK steps ahead in the cycle.

Formally, update every element as follows: Ai=Ai+A(i+K)(modN)A'i = A_i + A{(i+K) \pmod N}

Note: This transformation must be performed in-place with O(1)O(1) auxiliary space. The calculation for AiA'_i must use the values of AA before any updates were made.

Constraints

  • 1N1061 \le N \le 10^6
  • 1K<N1 \le K < N
  • 1Ai1041 \le A_i \le 10^4
  • All input values are integers.

Examples

Example 1
Input:4 1 1 2 3 4
Output:3 5 7 5
Accepted 5/16
Acceptance 31%
Loading editor...
Input
4 1 1 2 3 4
Expected Output
3 5 7 5
Custom Test Cases:
Input Expected Output