"I didn't submit... The f**king system didn't let me! It logged me out due to inactivity!" Raged and depressed, Justin walks out of the door of the SDIC exam venue. He is so sad. Can't even advance to the finals.

"Senpai, why you look so upset? What's wrong?"

"I don't want to explain, Korone... Just leave me alone."

"Oh."

Korone wants to cheer up her senpai. She knows that Justin has $n$ favourite positive integers, the $i$-th integer is denoted by $J_i$. She also has $n$ favourite positive integers, the $i$-th integer is denoted by $K_i$. To give Justin a surprise, she decided to find $x_i$ such that $$J_i \cdot x_i \equiv 1 \mod{K_i} \text{ and } 0 \lt x_i \lt K_i$$ for all $1 \le i \le n$. $x_i$ may not exist, in which case $x_i = 0$.

Korone can't do this on her own. Can you help her out?

Input

The first line of input contains an integer $n$.
The second line of input contains $n$ integers $J_1, J_2, \dots, J_n$.
The third line of input contains $n$ integers $K_1, K_2, \dots, K_n$.

Output

The only line of the output should contain $n$ integers $x_1, x_2, \dots, x_n$.

Subtasks

Subtask 1 (20%): $1 \le n \le 100; 1 \le K_i \le 1000; 1 \le J_i \le 10^9$
Subtask 2 (80%): $1 \le n \le 10^5; 1 \le K_i \le 10^9; 1 \le J_i \le 10^9$