Description

阿格尼與露娜除了烤肉以外最喜歡的就是玩雪了,今天他們要來堆雪人。
只是堆出來的雪人不知道為什麼野獸化變成了長毛的怪獸雪人,於是露娜對阿格尼說:「對他使用炎拳吧。」

話說回來阿格尼與露娜總共有 $a^ x$ 公斤的雪,一個雪人可以用 $b^ y$ 公斤的雪堆出來。
阿格尼與露娜想知道他們最多可以堆出幾個雪人,假設可以堆出 $A$ 個,並且堆完後會剩下 $B$ 公斤的雪,請你求出 $A,B$。
因為 $A,B$ 可能會很大,所以請輸出 $A\text{ mod }N$ 與 $B\text{ mod }M$。

Input Format

輸入一行,有 $6$ 個正整數,分別是 $a,b,x,y,N,M$。

對於所有測試資料:

  • $1\leq a,b,x\leq 10^ 9$
  • $2\leq N,M\leq 10^ 9$
  • $1\leq y\leq 1000$

Output Format

輸出 $A\text{ mod }N$ 與 $B\text{ mod }M$。

Sample Input 1

3 5 10 4 28 35

Sample Output 1

10 19

Sample Input 2

42 1 888 999 13579 12345

Sample Output 2

9498 0

Sample Input 3

48763 1 111111111 154 4949 1000

Sample Output 3

2199 0

Sample Input 4

10 2320 999998888 1 14107 1910

Sample Output 4

13943 320

Hints

在範例測資一:$a^ x=3^ {10}=59049,b^ y=5^ 4=625$,
可算出 $A=94,B=299$,$A\text{ mod }N=94\text{ mod }28=10$,$B\text{ mod }M=299\text{ mod }35=19$。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 1, 4~13 $x\leq 10^ 5,b=1$ 8
3 1~2, 4~20 $b=1$ 11
4 3, 21~32 $y=1,b<N,N$ 是質數 18
5 3, 21~48 $y=1$ 21
6 0~96 無其他限制 42

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 6
1 2000 65536 65536 1 2 3 6
2 2000 65536 65536 1 3 6
3 2000 65536 65536 1 4 5 6
4 2000 65536 65536 2 3 6
5 2000 65536 65536 2 3 6
6 2000 65536 65536 2 3 6
7 2000 65536 65536 2 3 6
8 2000 65536 65536 2 3 6
9 2000 65536 65536 2 3 6
10 2000 65536 65536 2 3 6
11 2000 65536 65536 2 3 6
12 2000 65536 65536 2 3 6
13 2000 65536 65536 2 3 6
14 2000 65536 65536 3 6
15 2000 65536 65536 3 6
16 2000 65536 65536 3 6
17 2000 65536 65536 3 6
18 2000 65536 65536 3 6
19 2000 65536 65536 3 6
20 2000 65536 65536 3 6
21 2000 65536 65536 4 5 6
22 2000 65536 65536 4 5 6
23 2000 65536 65536 4 5 6
24 2000 65536 65536 4 5 6
25 2000 65536 65536 4 5 6
26 2000 65536 65536 4 5 6
27 2000 65536 65536 4 5 6
28 2000 65536 65536 4 5 6
29 2000 65536 65536 4 5 6
30 2000 65536 65536 4 5 6
31 2000 65536 65536 4 5 6
32 2000 65536 65536 4 5 6
33 2000 65536 65536 5 6
34 2000 65536 65536 5 6
35 2000 65536 65536 5 6
36 2000 65536 65536 5 6
37 2000 65536 65536 5 6
38 2000 65536 65536 5 6
39 2000 65536 65536 5 6
40 2000 65536 65536 5 6
41 2000 65536 65536 5 6
42 2000 65536 65536 5 6
43 2000 65536 65536 5 6
44 2000 65536 65536 5 6
45 2000 65536 65536 5 6
46 2000 65536 65536 5 6
47 2000 65536 65536 5 6
48 2000 65536 65536 5 6
49 2000 65536 65536 6
50 2000 65536 65536 6
51 2000 65536 65536 6
52 2000 65536 65536 6
53 2000 65536 65536 6
54 2000 65536 65536 6
55 2000 65536 65536 6
56 2000 65536 65536 6
57 2000 65536 65536 6
58 2000 65536 65536 6
59 2000 65536 65536 6
60 2000 65536 65536 6
61 2000 65536 65536 6
62 2000 65536 65536 6
63 2000 65536 65536 6
64 2000 65536 65536 6
65 2000 65536 65536 6
66 2000 65536 65536 6
67 2000 65536 65536 6
68 2000 65536 65536 6
69 2000 65536 65536 6
70 2000 65536 65536 6
71 2000 65536 65536 6
72 2000 65536 65536 6
73 2000 65536 65536 6
74 2000 65536 65536 6
75 2000 65536 65536 6
76 2000 65536 65536 6
77 2000 65536 65536 6
78 2000 65536 65536 6
79 2000 65536 65536 6
80 2000 65536 65536 6
81 2000 65536 65536 6
82 2000 65536 65536 6
83 2000 65536 65536 6
84 2000 65536 65536 6
85 2000 65536 65536 6
86 2000 65536 65536 6
87 2000 65536 65536 6
88 2000 65536 65536 6
89 2000 65536 65536 6
90 2000 65536 65536 6
91 2000 65536 65536 6
92 2000 65536 65536 6
93 2000 65536 65536 6
94 2000 65536 65536 6
95 2000 65536 65536 6
96 2000 65536 65536 6