To read the problem statement in English, choose the language using the flag on the navigation bar.

Sau khi các thần dân đã được tiêm ngừa vaccine đầy đủ, đại dịch COVID-19 trên hành tinh mèo đã được đẩy lùi và cuộc sống dần ổn định trở lại. Để ăn mừng chiến thắng đại dịch, quốc vương hành tinh mèo đã tổ chức đại hội thể thao với nhiều môn thể thao khác nhau, trong đó có bộ môn Permeowtation (do Neko sáng tạo ra) với luật chơi như sau:

Ban đầu, vận động viên (VĐV) sẽ được cho hai hoán vị ~a~ và ~b~ có cùng độ dài ~n~. VĐV cần tiến hành trộn hai hoán vị với nhau để tạo ra dãy ~c~ gồm ~2 \cdot n~ phần tử như sau:

• Ban đầu, dãy ~c~ không chứa phần tử nào.

• VĐV thực hiện ~2\cdot n~ bước. Ở mỗi bước cần chọn dãy ~a~ hoặc dãy ~b~, rồi xóa phần tử đầu tiên khỏi dãy được chọn và thêm phần tử này vào cuối dãy ~c~. Lưu ý rằng, dãy được chọn cần có ít nhất một phần tử.

VĐV sẽ giành được tấm huy chương cao quý từ liên đoàn thể thao hành tinh mèo, nếu như dãy ~c~ mà VĐV tạo ra không có hai phần tử liên tiếp nào trùng nhau. Nói cách khác, VĐV cần tạo ra dãy ~c~ thỏa mãn với mọi ~1 \le i < 2 \cdot n~, ~c_i \ne c_{i + 1}~.

Mike, một trong những VĐV trẻ tuổi của bộ môn này, đã luyện tập rất chăm chỉ để có sự chuẩn bị tốt nhất. Tuy nhiên, trước áp lực sân khấu, cô đang cảm thấy rất hồi hộp và không còn nhớ cách để giành chiến thắng. Hãy giúp cô hoàn thành trò chơi này và giành được tấm huy chương nhé.

Định nghĩa. Hoán vị là một mảng số nguyên gồm ~n~ phần tử khác nhau từ ~1~ đến ~n~ theo thứ tự bất kì. Ví dụ, ~[2,3,1,5,4]~ là một hoán vị, nhưng ~[1,2,2]~ không phải là một hoán vị (giá trị ~2~ được lặp lại hai lần trong mảng) và ~[1,3,4]~ cũng không phải là hoán vị (độ dài mảng là ~n=3~ nhưng trong mảng có phần tử ~4~).

Input

Dòng đầu tiên gồm số nguyên ~n~ (~2 \le n \le 10^5~) là độ dài của hai hoán vị ~a~ và ~b~.

Dòng thứ hai gồm ~n~ số nguyên phân biệt ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~).

Dòng thứ ba gồm ~n~ số nguyên phân biệt ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le n~).

Output

In ra chuỗi gồm ~2n~ kí tự a hoặc b. Kí tự thứ ~i~ cho biết dãy cần được lựa chọn ở bước thứ ~i~.

Có thể chỉ ra rằng đáp án luôn tồn tại với giới hạn đề bài cho.

Scoring

• Subtask 1, tương ứng với ~15~ điểm, có ~n = 2~

• Subtask 2, tương ứng với ~15~ điểm ~n \le 10~

• Subtask 3, tương ứng với ~20~ điểm, Không có giới hạn gì thêm

Tổng cộng bài toán có ~50~ điểm.

Sample Input 1

3
1 2 3
3 2 1

Sample Output 1

abaabb

Sample Input 2

2
2 1
1 2

Sample Output 2

baab

Notes

Ở ví dụ đầu tiên đã cho, dãy ~a~ có giá trị ~[1, 2, 3]~ và dãy ~b~ có giá trị ~[3, 2, 1]~.

Với cách tạo dãy ~c~ ở output, ta thu được dãy ~[1, 3, 2, 3, 2, 1]~.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Trong giờ ra chơi, nhóm gồm ~n~ bạn học sinh rủ nhau chơi nhảy dây. Trong mỗi lượt chơi sẽ có hai bạn được chọn để quăng dây, và một bạn được chọn để nhảy dây. Hai bạn quăng dây sẽ cầm hai đầu sợi dây, một bạn quăng dây theo chiều kim đồng hồ, và bạn còn lại quăng ngược chiều kim đồng hồ, để dây liên tục chạm đất và quăng qua đầu người nhảy. Người nhảy phải đứng giữa hai người quăng và phải nhảy khi dây chạm đất. Nếu như dây chạm vào chân bạn nhảy, bạn nhảy sẽ thua cuộc.

Tất cả ~n~ bạn đều rất khỏe mạnh và năng động, nên các bạn có độ dẻo dai lần lượt là ~c_1, c_2, \ldots, c_n~.

Nếu như bạn thứ ~i~ được chọn làm bạn nhảy dây, trong ~c_i~ giây bạn ấy sẽ đứng ở trên mặt đất, sau đó bạn ấy nhảy và trong ~c_i~ giây tiếp theo chân bạn ấy không chạm đất, và quá trình này sẽ lặp lại. Ví dụ, nếu ~c_i = 3~:

• Tại giây ~1, 2, 3~ chân bạn ấy chạm đất.

• Tại giây ~4, 5, 6~ chân bạn ấy không chạm đất.

• Tại giây ~7, 8, 9~ chân bạn ấy chạm đất.

• Tại giây ~10, 11, 12~ chân bạn ấy không chạm đất.

• ~\ldots~

Nếu như bạn thứ ~u~ và ~v~ được chọn làm hai bạn cầm dây, dây mà hai bạn quăng sẽ chạm đất vào các thời điểm là bội của ~gcd(c_u, c_v)~, trong đó ~gcd(x, y)~ được định nghĩa là ước chung lớn nhất của hai số nguyên ~x~ và ~y~. Ví dụ, với ~c_u = 6~ và ~c_v = 8~, ~gcd(6, 8) = 2~, nên dây mà hai bạn này quăng sẽ chạm đất tại các giây ~2, 4, 6, 8, 10, \ldots~

Cho danh sách độ dẻo dai của ~n~ bạn. Với bạn thứ ~i~, hãy đếm xem có bao nhiêu cặp bạn quăng dây ~u~ và ~v~ (~u < v~), sao cho nếu như bạn thứ ~i~ là người nhảy dây, thì bạn này sẽ không bao giờ thua.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~3 \le n \le 10^6~) là số lượng bạn học sinh rủ nhau chơi nhảy dây.

Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le 10^6~) lần lượt là độ dẻo dai của ~n~ bạn học sinh.

Output

In ra ~n~ số nguyên. Số thứ ~i~ cần in ra là là số lượng cặp bạn học sinh có thể chọn làm bạn quăng dây sao cho nếu ~i~ được chọn làm bạn nhảy dây thì bạn này sẽ không bao giờ thua.

Scoring

• Subtask 1, ứng với ~65~ điểm, có ~n \le 100~.

• Subtask 2, ứng với ~65~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~130~ điểm.

Sample Input 1

3
1 6 8

Sample Output 1

1 0 0

Sample Input 2

12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 2

15 3 1 0 0 0 0 0 0 0 0 0

Notes

Trong ví dụ đầu tiên:

• Nếu bạn đầu tiên được chọn làm bạn nhảy, các thời điẻm chân của bạn ấy không chạm đất là các giây ~2, 4, 6, 8, \ldots~ do ~c_1 = 1~. Bạn thứ hai và ba có thể chọn làm cặp bạn quăng dây, do ~c_2 = 6, c_3 = 8~, ~gcd(6, 8) = 2~, và thời điểm dây mà hai bạn quăng chạm đất cũng sẽ là các giây ~2, 4, 6, 8, \ldots~.

• Nếu bạn thứ hai được chọn làm bạn nhảy, bạn ấy sẽ thua nếu bạn thứ nhất và thứ ba quăng dây, bởi vì ~gcd(1, 8) = 1~, do đó dây chạm đất tại mọi giây nguyên. Điều này cũng tương tự nếu bạn thứ ba được chọn làm bạn nhảy.

Fun fact: trong tiếng Anh, trò chơi được mô tả trong đề bài giống trò chơi Double Dutch hơn là trò chơi Skipping rope, nhưng được chơi bằng một dây thay vì hai dây.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Lộc thích màu lam đậm, nên lần đầu tiên mà Lộc đăng kí tài khoản trên một trang Online Judge giấu tên, Lộc đã quyết định sử dụng nickname darkcyan. Buồn thay, nickname này đã được sử dụng. Vì nickname bị trùng lặp, hệ thống có gợi ý Lộc sử dụng các nickname khác như darkcyan_no1, darkcyan_pro và darkcyan_vip, tuy nhiên Lộc không thích các nickname đó. Sau một hồi đắn đo suy nghĩ, nickname mà Lộc chọn là darkkcyan, rất gần với nickname ban đầu, nhưng kí tự k được nhân đôi lên. Và thật may mắn là nickname này chưa tồn tại! Nickname này đã được Lộc sử dụng cho hệ thống này cũng như trên nhiều nền tảng khác nhau.

Lộc nhận thấy rằng việc thay đổi nickname như thế thật là thú vị, và có thể áp dụng ý tưởng này để tạo ra một hệ thống gợi ý nickname hoàn toàn mới! Cụ thể, với một nickname được biểu diễn bởi xâu gồm ~k~ kí tự ~t_1 t_2 \ldots t_k~, hệ thống có thể biến đổi nickname sử dụng theo tác sau một số lần (có thể là 0 lần):

• Hệ thống chọn ra một số nguyên ~i~ (~1 \le i \le k~) tùy ý, và chèn một kí tự ~t_i~ vào ngay sau vị trí ~i~. Kí tự mới có chỉ số là ~i + 1~ và các kí tự sau đó có chỉ số được tăng lên một. Độ dài của nickname mới sẽ là ~k + 1~.

Ví dụ, với nickname darkcyan, với một thao tác có thể tạo ra xâu darkkcyan, ddarkcyan, và darkcyann, và với ba thao tác có thể tạo ra xâu ddaarrkcyan, darkkkkcyan hoặc ddarkkcyann.

Để đảm bảo độ tối ưu, hệ thống cần biến đổi nickname với số thao tác biến đổi ít nhất, sao cho nickname sau khi biến đổi chưa tồn tại trong hệ thông, để gợi ý cho người dùng.

Lộc nghĩ rằng sẽ thật đáng tiếc nếu như không có hệ thống gợi ý nickname trùng lặp nào sử dụng ý tưởng này. Do đó Lộc quyết định áp dụng luôn hệ thống gợi ý nickname này cho mạng xã hội Virtual Network for Online Intercommunication (VNOI) mà mình đang tham gia phát triển. Hiện tại trên mạng xã hội VNOI đã có ~n~ người dùng, và người dùng thứ ~i~ có nickname là xâu kí tự ~S_i~. Lộc muốn biết rằng, với mỗi nickname ~S_i~, nếu nếu như có một người dùng mới khi đăng kí hệ thống sử dụng nickname trùng với nickname này, vậy cần ít nhất bao nhiêu thao tác biến đổi nickname này để tạo ra một nickname chưa được sử dụng trên VNOI. Vì Lộc vẫn đang bận phát triển thành phần khác của hệ thống, nên Lộc muốn nhờ các bạn giải quyết bài toán này.

Cho danh sách nickname của ~n~ người dùng trên hệ thống, yêu cầu với mỗi nickname ~S_i~, cần in ra số lượng thao tác biến đổi ít nhất để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^6~) là số lượng người dùng mạng xã hội VNOI.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa xâu ~S_i~ (~1 \le |S_i| \le 10^6~, ~S_i~ chỉ chứa các kí tự tiếng Anh in thường) là nickname của người dùng thứ ~i~ trên hệ thống.

Dữ liệu đảm bảo tổng độ dài của tất cả các nickname trên hệ thống không quá ~10^6~ và không tồn tại hai nickname nào giống nhau.

Output

In ra ~n~ dòng. Dòng thứ ~i~ là số lượng thao tác biến đổi ít nhất để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống.

Scoring

• Subtask 1, tương ứng với ~55~ điểm, các kí tự trong cùng một nickname là giống nhau.

• Subtask 2, tương ứng với ~75~ điểm, không có ràng buộc gì thêm.

Tộng cộng bài toán có ~130~ điểm.

Sample Input 1

3
aaa
a
aa

Sample Output 1

1
3
2

Sample Input 2

3
ab
aab
abb

Sample Output 2

2
1
1

To read the problem statement in English, choose the language using the flag on the navigation bar.

FireGhost và những người bạn đang lên kế hoạch du lịch ở thành phố VNOI!

Có ~n~ điểm du lịch nổi tiếng trong thành phố. Để lên kế đi hoạch du lịch, những người bạn cần lên danh sách các địa điểm sẽ thăm quan. Vì vậy có tổng cộng ~2^n~ kế hoạch du lịch khác nhau, từ không thăm quan một địa điểm nào cả, cho đến thăm quan tất cả các địa điểm trong thành phố.

Tuy nhiên, không phải kế hoạch nào cũng làm hài lòng tất cả các bạn. FireGhost có ~m~ người bạn. Mỗi người sẽ có một danh sách các nguyện vọng, trong đó mỗi nguyện vọng sẽ có dạng "Tôi muốn tham quan điểm du lịch thứ ~p~" hoặc "Tôi không muốn tham quan điểm du lịch thứ ~p~". May mắn thay, mọi người đều dễ tính, nên mỗi người bạn sẽ cảm thấy hài lòng về chuyến đi khi ít nhất một nguyện vọng của mình được thỏa mãn trong kế hoạch du lịch.

FireGhost tò mò muốn biết có bao nhiêu cách để làm hài lòng tất cả bạn bè, các bạn hãy giúp FireGhost nhé!

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 10^5~, ~1 \le m \le 20~) lần lượt là số điểm du lịch và số người bạn của FireGhost.

Dòng thứ ~i~ trong ~m~ dòng tiếp theo bắt đầu bằng số nguyên dương ~k~ (~1 \leq k \leq n~) là số nguyện vọng của người bạn thứ ~i~, và theo sau là ~k~ số nguyên ~a_1, a_2, \ldots, a_k~ (~1 \le |a_j| \le n~) là mô tả các nguyện vọng.

• nếu ~a_j > 0~, người bạn thứ ~i~ có nguyện vọng tham quan địa điểm ~a_j~.

• ngược lại, nếu ~a_j < 0~, người bạn thứ ~i~ có nguyện vọng không tham quan địa điểm ~|a_j|~.

Dữ liệu đảm bảo ~|a_{u}| \neq |a_{v}|~ với mọi ~1 \le u < v \le k~.

Output

Một dòng duy nhất chứa số lượng kế hoạch du lịch làm hài lòng tất cả bạn bè của FireGhost. Vì số lượng kế hoạch có thể rất lớn, in ra kết quả theo modulo ~10^9 + 7~.

Scoring

• Subtask 1, tương ứng với ~30~ điểm, có ~n \leq 20~ và ~m \leq 5~

• Subtask 2, tương ứng với ~94~ điểm, có ~n \leq 10^3~ và ~m \leq 15~

• Subtask 3, tương ứng với ~180~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~304~ điểm.

Sample Input 1

4 2
2 1 -4
1 3

Sample Output 1

6

Sample Input 2

7 1
2 -2 6

Sample Output 2

96

Sample Input 3

6 3
3 1 4 -2
2 2 3
3 -5 2 -6

Sample Output 3

36

Notes

Ở test mẫu đầu tiên, những kế hoạch du lịch sau (danh sách các địa điểm) sẽ làm hài lòng tất cả bạn bè:

1. ~\{3\}~,

2. ~\{1, 3\}~,

3. ~\{2, 3\}~,

4. ~\{1, 2, 3\}~,

5. ~\{1, 3, 4\}~,

6. ~\{1, 2, 3, 4\}~.

Các kế hoạch du lịch còn lại sẽ làm ai đó không hài lòng. Ví dụ:

• Kế hoạch ~\{3, 4\}~ sẽ làm cho người bạn đầu tiên không hài lòng, vì bạn đầu tiên không muốn thăm quan địa điểm thứ ~4~.

• Kế hoạch ~\{1\}~ sẽ làm bạn thứ hai không hài lòng, khi mà địa điểm duy nhất mà bạn thứ hai muốn tham quan là địa điểm thứ ~3~.

• Kế hoạch ~\{4\}~ không làm ai hài lòng cả.

To read the problem statement in English, choose the language using the flag on the navigation bar.

Một đồ thị vô hướng được gọi là quả tạ nếu các đỉnh của nó có thể được chia thành ~2~ phần, trong đó:

• Mỗi cặp đỉnh trong cùng một phần đều có cạnh nối.

• Có chính xác một cạnh nối 2 đỉnh thuộc khác phần nhau.

Các đồ thị dưới đây là các đồ thị quả tạ:

Các đồ thị dưới đây không phải là các đồ thị quả tạ:

Từ trái qua phải, đồ thị đầu tiên có duy nhất một thành phần liên thông. Đồ thị thứ hai có một phía mà có hai cặp đỉnh không có cạnh nối giữa chúng, và đồ thị thứ ba không liên thông.

Cho một đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Đồ thị đã cho không có khuyên và không có nhiều hơn một cạnh nối giữa hai đỉnh bất kì. Hãy tính số lượng cạnh ít nhất cần thêm vào đồ thị để đồ thị trở thành đồ thị quả tạ.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~2 \le n \le 10^5~, ~0 \le m \le 10^5~), lần lượt là số lượng đỉnh và cạnh trong đồ thị.

Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le n~, ~u \ne v~), thể hiện có một cạnh nối giữa hai đỉnh ~u~ và ~v~.

Dữ liệu đảm bảo mỗi cạnh trong đồ thị xuất hiện duy nhất một lần.

Output

In ra một số nguyên dương duy nhất là số lượng cạnh ít nhất cần thêm vào để đồ thị đã cho trở thành một đồ thị quả tạ.

Nếu không tồn tại cách thêm cạnh nào để tạo ra đồ thị quả tạ, in ra ~-1~.

Scoring

• Subtask 1, ứng với ~125~ điểm, có ~n \le 500~.

• Subtask 2, ứng với ~285~ điểm, không có giới hạn gì thêm.

Tổng cộng bài toán có ~410~ điểm.

Sample Input 1

5 7
2 3
5 3
2 5
2 1
1 5
3 1
5 4

Sample Output 1

0

Sample Input 2

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

Sample Output 2

5

Sample Input 3

3 3
1 2
2 3
3 1

Sample Output 3

-1