Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Operations Modulo m

Continuing their research on graphics cards, the team has not reached a point where they need several calculations per pair of numbers. The team is currently testing their code, so they ask you to write a program that would validate addition, subtraction, and multiplication of numbers modulo m.
Given two lists of integers and , you are asked to calculate:
As it’s faster to perform similar calculations on a GPU, you are asked to first print all the results for addition, then all the results for subtraction, and then all the results for multiplication.

#### Input

The first line of the input contains two integers n (1 ≤ n ≤ 100 000) and m (1 ≤ m ≤ ).
The second line contains n space-separated integers ().
The next line contains n space-separated integers ().

#### Output

The first line of the output should contain all the additions separated by a space .
The second line should contain all the subtractions separated by a space .
The final line should contain all the multiplications separated by a space .

#### Examples

 Input Output 3 3 1 2 1 3 4 1 1 0 2 1 1 0 0 2 1

#### Explanation

1. Subtraction (the second line)
1. Multiplication (the third line)

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 3 MB