4493 - Mod Equation

Time Limit: 1s Memory Limit: 128MB

Submissions: 405 Solved: 117
Description

정수 a, b, c, d, n 에 대해

조건1: a × x + b × y를 n으로 나눈 나머지가 r이다.

조건2: c × x + d × y를 n으로 나눈 나머지가 s이다.

조건3: a × d - b × c와 n이 서로소다. (최대공약수가 1이다.)

위의 세 가지 조건을 만족하는 0 이상 n 미만의 정수 x와 y는 반드시 존재하며, 한 가지밖에 없다는 사실이 이미 증명되어있다.

주어진 a, b, c, d, r, s에 대해 위의 조건들을 만족하는 0 이상 n 미만의 정수 x, y를 구해보자.

 

Input

* Line 1 : n (2 ≤ n ≤ 100)

* Line 2 : a, b, r (-10000 ≤ a,b ≤ 10000, 0 ≤ r ≤ n-1)

* Line 3 : c, d, s (-10000 ≤ c,d ≤ 10000, 0 ≤ s ≤ n-1)

Output

* Line 1: 주어진 조건들을 만족하는 정수 x를 출력한다. (0 ≤ x ≤ n-1)

* Line 2: 주어진 조건들을 만족하는 정수 y를 출력한다. (0 ≤ y ≤ n-1)

Sample Input
11
-992 745 0
551 -1000 1
Sample Output
3
9
Hint

-3을 4로 나눈 0이상 4미만의 나머지는 1입니다

하지만 컴퓨터는 -3%4를 -3으로 계산하기 때문에 나머지를 음이 아닌 정수로 변환해주는 과정이 필요합니다