Cho 2 số ~x~ và ~y~. Đếm số lượng số nguyên dương ~a~ sao cho ~lcm(a,x)=y~.

~lcm(u, v)~, với ~u, v~ là hai số nguyên dương, được định nghĩa là số nguyên dương ~k~ bé nhất sao cho ~k~ đồng thời chia hết cho cả ~u~ và ~v~.

Input

Một dòng duy nhất gồm ~2~ số ~x~ và ~y~ (~1 \le x,y \le 10^{12}~).

Output

Gồm ~1~ dòng là số lượng số nguyên dương ~a~ thỏa điều kiện đề bài.

Scoring

• Subtask 1 (~50\%~): ~x~ = ~y~.

• Subtask 2 (~50\%~): Không có ràng buộc gì thêm.

Sample Input 1

2 2

Sample Output 1

2

Notes

Có ~2~ số ~a~ thỏa ~lcm(a, x) = y~ là ~1~ và ~2~.

Pemguimn nhặt được mảnh giấy ghi các dòng code của một chương trình như sau:

void dfs(int i, int pre){
    time_in[i] = ++timedfs;
    for(int x : adj[i]){
        if(x == pre) continue;
        dfs(x, i);
    }
    time_out[i] = timedfs;
}

void main(){
    // dựng cây
    dfs(1, -1);
}

• Được biết, đoạn code trên là mã của một thuật toán nổi tiếng, đường đi Euler trên cây. Ngoài ra, khi tìm được các cạnh của cây thì Pemguimn sẽ biết được mật mã dẫn đến thế giới Anime.

• Tuy nhiên, cây đã bị giấu mất, và Pemguimn chỉ biết được giá trị của mảng timein[] và timeout[] cũng như giá trị ~n~, số đỉnh của cây. Các bạn hãy giúp Pemguimn mở được cánh cổng tới thế giới của harem nhé!

• Ngoài ra, tồn tại trường hợp ai đó đã chơi khăm Pemguimn và thay đổi giá trị của mảng timein[] hoặc timeout[] nên không tồn tại cây thỏa giá trị của hai mảng trên. Trong trường hợp đó, hãy in ra ~-1~ trên một dòng duy nhất.

Yêu cầu

Cho giá trị ~n~, số đỉnh của cây , và giá trị của các mảng timein[], timeout[] của từng đỉnh được mô tả như trên.

Với mỗi đỉnh ~i~, bạn hãy in ra số đỉnh kể với đỉnh ~i~ trong cây và in ra số hiệu của các đỉnh đấy.

Input

• Dòng đầu chứa ~n~, số đỉnh của cây, ~n~ (~1 \leq n \leq 5 \cdot 10^5~).

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai giá trị timein[i] và timeout[i], (~1 \leq~ timein[i], timeout[i] ~\leq n~), lần lượt là giá trị của giá trị timein và timeout của đỉnh thứ ~i~.

Output

Trong trường hợp tồn tại đáp án:

• In đáp án trên ~2 \times n~ dòng:

  • Dòng thứ ~2 \times i - 1~ in ra ~m~, số đỉnh kề với đỉnh ~i~ trong cây.

  • Dòng thứ ~2 \times i~ in ra ~m~ số, số hiệu của các đỉnh kề với ~i~ được liệt kê theo thứ tự tăng dần, cách nhau bởi dấu cách.

Trong trường hợp không tồn tại cây thỏa đề bài thì in ra ~-1~ trên một dòng duy nhất.

Scoring

• Subtask 1 (~25\%~): ~n \leq 10~.

• Subtask 2 (~25\%~): ~n \leq 100~.

• Subtask 3 (~50\%~): Không có ràng buộc gì thêm.

Sample Input 1

4
1 4
2 4
3 3
4 4

Sample Output 1

1
2 
3
1 3 4 
1
2 
1
2

Notes

• Trong test ví dụ trên, đỉnh ~1~ kề với ~1~ đỉnh duy nhất trong cây, là đỉnh ~2~.

• Tương tự, đỉnh ~2~ kề với ~3~ đỉnh là ~1, 3~ và ~4~.

• Đỉnh ~3~ và ~4~ chỉ kề với một đỉnh duy nhất là đỉnh ~2~.

Cho mảng ~a~ độ dài ~n~, mảng ~b~ độ dài ~m~. Ta định nghĩa hàm ~f(x)~ như sau: $$f(x) = \sum_{i=1}^{n} (a_i \bmod x)$$

Tìm ~j~ (~1 \leq j \leq m~) sao cho giá trị ~f(b_j)~ nhỏ nhất.

Input

• Dòng đầu chứa 2 số nguyên ~n, m~ (~1 \leq n, m \leq 5 \times 10^5~).

• Dòng tiếp theo gồm ~n~ số nguyên dương biểu diễn mảng ~a~, số thứ ~i~ là ~a_i~ (~1 \leq i \leq n~).

• Dòng tiếp theo gồm ~m~ số nguyên dương biểu diễn mảng ~b~, số thứ ~i~ là ~b_i~ (~1 \leq i \leq m~).

• ~1 \leq a_i, b_i \leq 5 \times 10^6~.

Output

In ra một số nguyên duy nhất là giá trị ~f(b_j)~ nhỏ nhất (~1 \leq j \leq m~).

Scoring

• Subtask 1 (~30\%~): ~n, m \leq 5 \times 10^3~.

• Subtask 2 (~40\%~): ~a_i, b_j \leq 10^5~ (~1 \leq i \leq n~, ~1 \leq j \leq m~).

• Subtask 3 (~30\%~): Không có giới hạn gì thêm.

Sample Input 1

5 3
5 3 4 2 1
6 3 4

Sample Output 1

6

Notes

Với test ví dụ:

• ~f(6)=15~.

• ~f(3)=6~.

• ~f(4)=7~.

~\Rightarrow~ ~f(3)=6~ là đáp án tối ưu.

~dwuy~ hiện sống ở thành phố XYZ gồm ~n~ góc đường và ~m~ con đường, con đường thứ i nối góc đường ~u_i~ và ~v_i~, tốn ~c_i~ giây để đi hết con đường. Tại thành phố này còn có ~k~ cô người yêu của cậu. ~dwuy~ sống tại góc đường ~1~ và cô người yêu thứ ~i~ sống tại ngôi nhà ở góc đường ~x_i~.

Mỗi góc đường ở thành phố XYZ sẽ có một trụ đèn giao thông có hai màu xanh và đỏ. Nếu tín hiệu đèn đang là màu đỏ thì người đi đường sẽ phải dừng lại cho đến khi đèn giao thông chuyển sang màu xanh. Các trụ đèn đều có thời gian dừng đèn đỏ là ~R~ và thời gian cho đèn xanh là ~G~. Thời gian trên trụ đèn sẽ đếm ngược từ ~R~ giây đèn đỏ về ~1~ sau đó chuyển sang ~G~ giây đèn xanh, và ngược lại. Đèn xanh và đỏ sẽ hiện xen kẽ nhau ~R~ giây đèn đỏ xong đến ~G~ giây đèn xanh xong đến ~R~ giây đèn đỏ...

Tại thời điểm bắt đầu (thời điểm ~0~) trụ đèn tại góc đường thứ ~i~ sẽ là đèn xanh với ~t_i~ thời gian đếm ngược.

Mỗi ngày ~dwuy~ đều sẽ đến thăm ~k~ cô người yêu, nhưng thật không may hôm nay ~dwuy~ có hẹn với cô người yêu mới quen nên phải dành cả ngày cho cô ấy. Vì vậy ~dwuy~ chỉ có thể đến thăm duy nhất một cô trong ~k~ cô người yêu. Dữ liệu đảm bảo ~dwuy~ có đi đến mọi góc đường.

Yêu cầu:

Là bạn thân của ~dwuy~, bạn hãy giúp ~dwuy~ tính thời gian nhanh nhất để thăm cô người yêu thứ ~i~ (~1 \leq i \leq k~) và trở về nhà. Thời điểm ~dwuy~ bắt đầu đi từ nhà được tính là thời điểm ~0~.

Input

• Dòng đầu chứa năm số nguyên ~n, m, k, G, R~ — số góc đường, số con đường, số cô người yêu, thời gian mà ~dwuy~ phải chờ đen xanh và đỏ (~1 \leq k < n \leq 5 \times 10^4~, ~1 \leq m \leq 10^5~, ~1 \leq G \leq 20~, ~0 \leq R \leq 20~).

• Dòng thứ hai chứa ~k~ số nguyên ~x_1, x_2, \cdots, x_k~ — nơi ở của các cô người yêu của ~dwuy~ (~1 \leq x_i \leq n~).

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, c_i~ mô tả một cạnh của đồ thị (~1 \leq u_i, v_i \leq n~, ~1 \leq c_i \leq 10^9~).

• Dòng cuối cùng chứa ~n~ số nguyên ~t_1, t_2, \cdots, t_n~ — số giây đèn xanh ở mỗi góc đường tại thời điểm ~0~ (~1 \leq t_i \leq G~).

Output

Trên một dòng, in ra ~k~ số nguyên ~ans_1, ans_2, \cdots, ans_k~ lần lượt là thời gian nhanh nhất để thăm từng cô người yêu và trở về nhà.

Scoring

• Subtask 1 (~20\%~): ~R = 0~.

• Subtask 2 (~30\%~): ~1 \leq k \leq 10~.

• Subtask 3 (~50\%~): Không có ràng buộc gì thêm.

Sample Input 1

6 8 5 6 0
2 3 4 5 6
1 2 6
2 3 6
1 4 1
2 5 2
5 6 4
6 2 4
2 4 4
2 6 6
1 4 6 2 4 4

Sample Output 1

10 22 2 14 18

Sample Input 2

6 8 2 4 5
2 3
6 2 3
6 4 2
6 5 1
1 4 6
1 5 7
2 3 5
2 4 4
4 5 1
4 3 1 3 2 3

Sample Output 2

23 41

Cho hai dãy ~a~ và ~b~ có cùng độ dài ~n~ và một số nguyên ~k~. Ta sẽ cắt dãy ~a~ ra thành ~k~ đoạn con liên tiếp sao cho mỗi đoạn con có độ dài tối thiểu là ~1~ và mọi phần tử của dãy ~a~ đều thuộc ~1~ trong ~k~ đoạn con này. Làm điều tương tự với dãy ~b~.

Gọi ~s_1, s_2, \cdots, s_k~ là tổng các phần tử của từng đoạn con của ~a~ và ~t_1, t_2, \cdots, t_k~ là tổng các phần tử của từng đoạn con của ~b~. Hãy tìm cách cắt dãy ~a~ và ~b~ sao cho biểu thức sau được cực đại hóa:

$$\sum_{j = 1}^{k} |s_j - t_j|$$

Input

Input sẽ được đưa ra theo format sau:

n k
a[1] a[2] a[3] ... a[n]
b[1] b[2] b[3] ... b[n]

Output

Gồm một số nguyên dương duy nhất, là đáp án cho bài toán trên.

Scoring

• Subtask 1 (~30\%~): ~2 \leq k, n \leq 12~.

• Subtask 2 (~20\%~): ~2 \leq n \leq 5*10^3~ và ~k = 2~.

• Subtask 3 (~50\%~): ~2 \leq n \leq 5 * 10^3~ và ~2 \leq k \leq 10~.

Sample Input 1

9 3
2 4 -5 3 9 1 -2 -7 10
-2 -3 1 0 3 8 -9 2 -4

Sample Output 1

61

Notes

Ta tách hai dãy ~a, b~ như sau:

- ~a = [2, 4, -5, 3, 9, 1], [-2, -7], [10]~.

- ~b = [-2, -3], [1, 0, 3, 8], [-9, 2, -4]~.

Khi đó, giá trị của mảng ~s, t~ là:

- ~s = [14, -9, 10]~.

- ~t = [-5, 12, -11]~.

Đáp án cuối cùng là ~|14 - (-5)| + |(-9) - 12| + |10 - (-11)| = 61~.