Calculate the Sum Modulo m
Operations on a graphics card (a GPU) are very parallelizable. So, if it’s possible to perform the same type of operation on many numbers simultaneously, it would be faster than performing different types of operations. The team is currently testing their code, so they ask you to write a program that would validate an addition of many numbers modulo a different number.
Given two lists of integers
Note that different languages implement the modulo operation differently. Python always makes sure that the result is positive. Yet, languages like C++ can give negative results after modulo (-3 % 2 → -1). A very popular trick is to add the modulo
m to the result if it’s negative with an if statement. A more generic way of handling such cases is by adding m and taking the modulo again: ((a % m) + m) % m. This would make sure that the result is always positive.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000) the number of elements.The second line contains
n space-separated integers The next line contains
n space-separated integers The last line contains
n space-separated integers Output
The program should print
n space-separated integers - Examples
Input | Output |
3
1 2 1
3 4 1
2 5 3 | 0 1 2 |
Explanation
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB