Năm nay, lần đầu tiên Eurokod được tổ chức — một cuộc thi quốc tế về viết code đẹp và dễ đọc!

Có ~n~ thí sinh tham gia cuộc thi, được đánh số từ ~1~ đến ~n~, mỗi người đã viết một đoạn code.

Các đoạn code được đánh giá bởi một hiệp hội các nhà khoa học máy tính. Hiệp hội gồm một chủ tịch và các thành viên. Chủ tịch cho điểm theo một cách, còn các thành viên cho điểm theo một cách khác.

Điểm của chủ tịch:

Chủ tịch sẽ xếp hạng các đoạn code từ đẹp nhất đến kém đẹp nhất (theo ý ông ấy). Đoạn code đứng đầu được ~n~ điểm, mỗi đoạn tiếp theo được ít hơn đoạn trước ~1~ điểm.

Điểm của các thành viên hiệp hội:

Mỗi thành viên hiệp hội bỏ phiếu cho đoạn code mà mình cho là đẹp nhất. Sau khi tất cả thành viên đã bỏ phiếu, các đoạn code được xếp theo thứ tự giảm dần của số phiếu nhận được. Đoạn code nhiều phiếu nhất được ~n~ điểm, mỗi đoạn tiếp theo được ít hơn đoạn trước ~1~ điểm.

Tổng điểm:

Tổng điểm của mỗi đoạn code bằng tổng số điểm do chủ tịch và số điểm do các thành viên hiệp hội cho.

Nhiệm vụ của bạn là in ra thứ tự các đoạn code theo chiều giảm dần của tổng điểm.

Nếu nhiều đoạn code có cùng tổng điểm thì đoạn được xếp trên là đoạn giành được nhiều điểm hơn từ các thành viên hiệp hội.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số thí sinh.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~, trong đó số thứ ~i~ là nhãn của đoạn code mà chủ tịch xếp thứ ~i~. Thứ tự xếp hạng của chủ tịch được cho từ đẹp nhất đến kém đẹp nhất, và chứa mọi nhãn từ ~1~ đến ~n~ đúng một lần.
• Dòng thứ ba chứa ~n~ số nguyên ~b_i~, trong đó số thứ ~i~ là số phiếu mà đoạn code thứ ~i~ nhận được từ các thành viên hiệp hội. Không có hai đoạn code nào nhận cùng số phiếu.

Kết quả

In ra ~n~ dòng — bảng xếp hạng các đoạn code theo chiều giảm dần của tổng điểm.

Mỗi dòng có dạng [hạng]. Kod[nhãn] ([số điểm]), trong đó [hạng] là hạng của đoạn code, [nhãn] là nhãn của đoạn code viết dưới dạng hai chữ số có thêm số ~0~ ở đầu nếu cần, và [số điểm] là tổng điểm của đoạn code.

Ví dụ, nếu hạng nhất thuộc về đoạn code có nhãn ~3~ với ~12~ điểm thì dòng đầu tiên là 1. Kod03 (12).

Ví dụ

Đầu vào:

3
1 2 3
50 10 20

Đầu ra:

1. Kod01 (6)
2. Kod03 (3)
3. Kod02 (3)

Giải thích: Kod03 và Kod02 có cùng tổng điểm, nhưng Kod03 nhận được nhiều phiếu hơn từ các thành viên hiệp hội nên được xếp trên.

Giới hạn

• ~1 \le n \le 50~
• ~1 \le a_i \le n~
• ~0 \le b_i \le 200~

Dãy ~a~ là một phép hoán vị của ~1..n~, và không có hai đoạn code nào nhận cùng số phiếu.

Vrsar là một thị trấn nhỏ ven biển gồm ~n~ quả đồi. Điều đáng ngạc nhiên là khi nhìn từ biển, các quả đồi xếp thành một hàng nối tiếp nhau sao cho quả đồi thứ ~i~ cách biển ~x_i~ mét. Trên đỉnh mỗi quả đồi có một sân trượt băng. Tất cả các sân trượt băng mở cửa cùng lúc, nhưng không đóng cửa cùng lúc: sân thứ ~i~ mở trong ~t_i~ phút.

Iva và Mia đến Vrsar và sẽ ở đây ~m~ ngày. Hai bạn rất thích trượt băng và muốn trượt băng mỗi ngày. Vào đầu ngày thứ ~i~, hai bạn ở vị trí cách biển ~a_i~ mét, và cuộc phiêu lưu trượt băng bắt đầu đúng lúc các sân trượt mở cửa. Để tới một sân trượt, hai bạn phải đi bộ tới đó với tốc độ một mét mỗi phút. Hai bạn có thể đi cả sang trái và sang phải. Nếu đang ở vị trí có một quả đồi, hai bạn có thể leo lên và tới sân trượt trên đỉnh, hoặc đi qua nó mà không leo.

Hai bạn có thể lực rất tốt nên leo đồi không mất thêm thời gian. Khi đã lên tới đỉnh, hai bạn có thể trượt băng bao lâu tùy ý cho tới khi sân trượt đóng cửa. Đi xuống thì không dễ như đi lên: trời vừa mưa nên mặt đất trơn, việc xuống quả đồi thứ ~i~ mất ~s_i~ phút. Sau khi xuống khỏi một quả đồi, hai bạn có thể tiếp tục đi bộ tới sân trượt tiếp theo.

Iva và Mia muốn biết số phút trượt băng nhiều nhất mà hai bạn có thể đạt được mỗi ngày. Trong một ngày, hai bạn có thể ghé bao nhiêu sân trượt cũng được. Hãy giúp hai bạn nhé!

Lưu ý: Nếu đầu ngày Iva và Mia ở đúng vị trí của một quả đồi thì hai bạn đang ở chân đồi, nên vẫn phải leo lên nếu muốn trượt băng trên đỉnh.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số quả đồi và số ngày.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i~, ~t_i~ và ~s_i~ — khoảng cách của quả đồi thứ ~i~ tới bờ biển, thời điểm đóng cửa của sân trượt, và thời gian cần để xuống khỏi quả đồi đó.
• Dòng cuối chứa ~m~ số nguyên ~a_i~ — khoảng cách của Iva và Mia tới bờ biển vào đầu ngày thứ ~i~.

Kết quả

In ra trên một dòng gồm ~m~ số nguyên, số thứ ~i~ là thời gian trượt băng nhiều nhất mà Iva và Mia đạt được trong ngày thứ ~i~.

Ví dụ

Đầu vào:

3 1
3 7 0
6 11 3
10 13 5
1

Đầu ra:

6

Giải thích: Hai bạn ở vị trí ~1~. Đi bộ ~2~ phút tới sân trượt trên quả đồi ở vị trí ~3~ và trượt băng ở đó ~5~ phút. Sau đó xuống đồi (mất ~0~ phút), đi bộ tiếp ~3~ phút tới sân trượt trên quả đồi ở vị trí ~6~ và trượt ở đó ~1~ phút. Tổng cộng hai bạn trượt băng được ~5 + 1 = 6~ phút.

Giới hạn

• ~1 \le n, m \le 10^5~
• ~0 \le x_i, t_i, s_i \le 10^9~
• ~0 \le a_i \le 10^9~

Silvia đang ở nhà ga Milano Centrale và nhận ra nhà ga có rất nhiều đường ray. Cô ấy thấy như vậy là quá nhiều, nên quyết định kiểm tra xem thực sự cần bao nhiêu đường ray.

Silvia cũng để ý một điều thú vị ở nhà ga này: lịch trình đến và đi lặp lại sau mỗi hai ngày, và hơn nữa lịch trình được sắp sao cho tất cả ~n~ đoàn tàu đều đến ga trong một ngày, rồi rời ga vào ngày hôm sau. Như vậy sẽ không có tàu nào rời đi trước khi mọi tàu đã đến.

Các đường ray ở nhà ga đủ dài để cả ~n~ đoàn tàu có thể xếp nối tiếp nhau trên cùng một đường ray. Tuy nhiên, nếu tàu ~x~ vào đường ray trước, rồi đến tàu ~y~, thì tàu ~x~ không thể rời đường ray trước tàu ~y~.

Silvia muốn biết số đường ray ít nhất cần dùng để tất cả các đoàn tàu có thể xếp lên các đường ray, mà không xảy ra tình huống một đoàn tàu không thể rời đi vì phía trước nó còn một đoàn tàu chưa rời.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số đoàn tàu.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~, cho biết đoàn tàu thứ ~i~ đến ga ở vị trí thứ ~a_i~ trong ngày thứ nhất. Dãy ~(a_i)~ là một phép hoán vị.
• Dòng thứ ba chứa ~n~ số nguyên ~b_i~, cho biết đoàn tàu thứ ~i~ rời ga ở vị trí thứ ~b_i~ trong ngày thứ hai. Dãy ~(b_i)~ là một phép hoán vị.

Kết quả

In ra trên dòng duy nhất số đường ray ít nhất cần dùng.

Ví dụ

Đầu vào:

5
3 5 2 4 1
3 2 5 1 4

Đầu ra:

2

Giải thích: Trên một đường ray, các đoàn tàu xếp nối tiếp nhau nên thứ tự rời đi phải ngược với thứ tự vào. Xét hai đoàn tàu vào ga đầu tiên: đoàn vào thứ ~1~ rời thứ ~4~, còn đoàn vào thứ ~2~ rời thứ ~5~. Nếu chúng ở cùng một đường ray thì đoàn vào sau phải rời trước, nhưng ở đây đoàn vào sau lại rời muộn hơn — vô lý. Vậy cần ít nhất ~2~ đường ray, và ~2~ đường ray là đủ.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le a_i \le n~, ~a_i \ne a_j~ với mọi ~i \ne j~
• ~1 \le b_i \le n~, ~b_i \ne b_j~ với mọi ~i \ne j~

Đến Szeged, ông Malnar như thường lệ có nghĩa vụ tìm hiểu văn hóa địa phương, và vì thế phải thử tất cả các món ăn truyền thống, các đặc sản và đồ uống địa phương.

Ta có thể hình dung Szeged gồm ~n~ địa điểm thú vị được đánh số từ ~1~ đến ~n~, nối với nhau bởi ~n - 1~ con đường hai chiều sao cho giữa mọi cặp địa điểm đều có một đường đi. Điều đáng ngạc nhiên là ông Malnar mất đúng một phút để đi hết mỗi con đường. Thời gian ở lại trong một địa điểm là không đáng kể.

Ông Malnar có danh sách ~m~ nhà hàng muốn ghé. Danh sách gồm ~m~ số nguyên dương, số thứ ~i~ là địa điểm mà gần đó có nhà hàng thứ ~i~.

Vấn đề là ông Malnar phải ăn kem ở một quán kem ngay sau khi ăn ở một nhà hàng. Một vấn đề khác là ông không chịu ghé cùng một quán kem hai lần.

May thay ông đã chuẩn bị trước: ông biết ~m~ quán kem, vị trí của chúng được cho bởi một danh sách ~m~ số nguyên dương, số thứ ~i~ là địa điểm mà gần đó có quán kem thứ ~i~.

Ông Malnar đã mệt sau chuyến đi và không muốn đi bộ nhiều hơn mức cần thiết, nên ông nhờ bạn tính xem ông sẽ phải đi bộ bao nhiêu, và cho biết thứ tự ghé các nhà hàng và quán kem.

Ông Malnar hiện đang ở địa điểm số ~1~ và phải quay lại đó khi kết thúc chuyến đi bộ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số địa điểm thú vị và số nhà hàng/quán kem.
• Dòng thứ hai chứa ~m~ số nguyên ~a_i~ — danh sách các nhà hàng.
• Dòng thứ ba chứa ~m~ số nguyên ~b_i~ — danh sách các quán kem.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~ — có một con đường giữa hai địa điểm ~x_i~ và ~y_i~.

Kết quả

• Dòng đầu tiên in ra ~t~ — số phút ông Malnar phải đi bộ để ghé hết các nhà hàng và quán kem, rồi quay lại địa điểm ~1~.
• Dòng thứ hai in ra ~2m~ số nguyên ~v_i~ — thứ tự ghé các nhà hàng và quán kem.

Các số ở vị trí lẻ là chỉ số nhà hàng và phải tạo thành một phép hoán vị của ~1..m~. Các số ở vị trí chẵn là chỉ số quán kem và cũng phải tạo thành một phép hoán vị của ~1..m~.

Việc ghé các địa điểm theo thứ tự đã cho rồi quay về vị trí xuất phát, luôn đi theo đường ngắn nhất giữa hai điểm liên tiếp, phải mất đúng ~t~ phút.

Nếu có nhiều thứ tự tối ưu, in ra một thứ tự bất kỳ.

Ví dụ

Đầu vào:

3 1
2
3
1 2
1 3

Đầu ra:

4
1 1

Giải thích: Ông Malnar trước tiên đi ~1~ phút tới nhà hàng duy nhất ở địa điểm ~2~, rồi ~2~ phút tới quán kem duy nhất ở địa điểm ~3~, và cuối cùng ~1~ phút để về địa điểm ~1~. Tổng cộng ông đi ~1 + 2 + 1 = 4~ phút.

Giới hạn

• ~1 \le m \le n \le 3 \cdot 10^5~
• ~1 \le a_i \le n~, ~a_i \ne a_j~ với mọi ~i \ne j~
• ~1 \le b_i \le n~, ~b_i \ne b_j~ với mọi ~i \ne j~
• ~1 \le x_i, y_i \le n~

Điểm của một subtask bằng điểm nhỏ nhất đạt được trên một test nào đó thuộc subtask đó.

Vito sống trong một thành phố có ~n~ công viên được đánh số từ ~1~ đến ~n~. Các công viên được nối bởi ~n - 1~ con đường sao cho giữa mọi cặp công viên đều có một đường đi. Mỗi công viên có một giá trị đẹp; giá trị đẹp của công viên thứ ~i~ là ~v_i~.

Đêm qua Vito quyết định đi lang thang quanh thành phố theo cách sau: sau khi tới một công viên, anh chọn một con đường với xác suất bằng nhau và đi tới công viên mà con đường đó dẫn tới. Nhưng trước khi khởi hành, anh nhìn qua cửa sổ toà nhà cao tầng của mình và thấy rằng trên mỗi con đường có một con rắn xanh hoặc một con rắn đỏ. Rắn xanh tấn công tất cả những người đi từ công viên có nhãn nhỏ hơn sang công viên có nhãn lớn hơn, còn rắn đỏ tấn công tất cả những người đi từ công viên có nhãn lớn hơn sang công viên có nhãn nhỏ hơn.

Vì Vito không muốn bị rắn tấn công, anh quyết định đổi kế hoạch: khi chọn một con đường ngẫu nhiên, anh chỉ xét những con đường mà anh sẽ không bị rắn tấn công. Vì anh thích đi bộ đường dài, anh sẽ không dừng lại cho tới khi không còn con đường nào có thể đi qua an toàn.

Và khi Vito đi xuống cầu thang toà nhà, anh hoàn toàn quên mất con đường nào có rắn đỏ hay rắn xanh, nên anh tự hỏi: nếu trên mỗi con đường xác suất có rắn xanh và rắn đỏ là bằng nhau, thì giá trị đẹp kỳ vọng của chuyến đi bắt đầu từ công viên thứ ~i~ là bao nhiêu?

Giá trị đẹp của một đường đi là tổng giá trị đẹp của các công viên được thăm trên đường đi đó. Giá trị đẹp kỳ vọng của chuyến đi được định nghĩa là tổng, trên mọi đường đi có thể, của tích giữa giá trị đẹp của đường đi đó và xác suất Vito đi theo đường đi đó.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số công viên.
• Dòng thứ hai chứa ~n - 1~ số nguyên ~p_i~ (~1 \le p_i < i~), cho biết có một con đường giữa công viên thứ ~(i+1)~ và công viên thứ ~p_i~.
• Dòng thứ ba chứa ~n~ số nguyên ~v_i~ — giá trị đẹp của công viên thứ ~i~.

Kết quả

Nếu giá trị đẹp kỳ vọng của chuyến đi bắt đầu tại công viên thứ ~i~ là ~\dfrac{a}{b}~ với ~a~, ~b~ nguyên, thì ở dòng thứ ~i~ hãy in ra ~a \cdot b^{-1} \pmod{10^9 + 7}~, trong đó ~b^{-1}~ là nghịch đảo modulo của ~b~ theo modulo ~10^9 + 7~.

Ví dụ

Đầu vào:

2
1
2 1

Đầu ra:

500000006
2

Giải thích: Cây chỉ gồm hai công viên nối với nhau bởi một con đường, với ~v_1 = 2~ và ~v_2 = 1~.

Bắt đầu từ công viên ~1~: đi từ ~1~ sang ~2~ là đi từ nhãn nhỏ sang nhãn lớn nên bị rắn xanh tấn công. Vậy Vito chỉ đi được nếu con rắn là đỏ (xác suất ~\tfrac{1}{2}~), khi đó anh sang công viên ~2~ rồi không đi tiếp được nữa, thu ~2 + 1 = 3~. Nếu con rắn là xanh thì anh không đi đâu được, chỉ thu ~2~. Kỳ vọng là ~\dfrac{3 + 2}{2} = \dfrac{5}{2}~, và ~5 \cdot 2^{-1} \equiv 500000006 \pmod{10^9+7}~.

Bắt đầu từ công viên ~2~: tương tự, kỳ vọng là ~\dfrac{3 + 1}{2} = 2~.

Giới hạn

• ~2 \le n \le 10^6~
• ~1 \le p_i < i~
• ~0 \le v_i \le 10^6~

Điểm của một subtask bằng điểm nhỏ nhất đạt được trên một test nào đó thuộc subtask đó. Lưu ý rằng ~n~ có thể lên tới ~10^6~ và cây có thể là một đường thẳng, nên hãy tránh đệ quy sâu khi duyệt cây.