Algorithms and Data Structures

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 and , you are asked to calculate the sum of each pair and modulo :
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 (1 ≤ ≤ ).

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

To check your solution you need to sign in