Giải bài trực tuyến

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/pagoda

Đầu năm mới Kỷ Sửu tượng phật ở chùa Bái Đính - ngôi chùa to nhất Đông Nam Á đã được làm lễ nhập thần. Chùa Bái Đính nằm ở trên một ngọn đồi cao, có đường bậc thang dẫn từ chân đồi lên gồm n bậc. Để làm tăng ý nghĩa tâm linh của khu chùa người ta thiết kế đặt các tượng ở các bậc thang, mỗi bậc thang đặt ba bức tượng: một bức đặt ở giữa và hai bức đặt ở hai bên. Hai bên là hai dãy tượng của các vị cao tăng, có người chắp tay đón chào phật tử về hành hương vãn cảnh chùa, có người cầm một số nén nhang. Giữa đường đi là dãy tượng của các tín đồ, một số người chắp tay, một số người khác có cầm trong tay vài thẻ hương đón chào khách hành hương. Số thẻ hương hoặc nén nhang ở mỗi bức tượng là không quá 9.

Ý tưởng của nhà Phật là nếu nhìn từ dưới chân đồi lên số nén nhang mà mỗi vị cao tăng cầm được hiểu như một chữ số hệ đếm thập phân, những tượng chắp tay biểu diễn số 0. Hai dãy các chữ số tương ứng với số nén nhang mà các vị cao tăng cầm trên tay ở hai dãy tượng cao tăng sẽ tạo thành hai số, mỗi số có n chữ số tượng trưng cho lượng từ bi mà Đức Phật ban phát. Khi đi từ dưới lên, hai vị cao tăng đầu tiên ở cả hai bên đều cầm nhang. Số thẻ hương tín đồ cầm cũng tượng trưng cho chữ số bằng số thẻ hướng trên tay, những tượng không cầm hương thể hiện chữ số 0. Những tượng tín đồ đứng đầu có thể có hoặc không cầm hương. Dãy số nguyên tương ứng với số thẻ hương trong tay các tín đồ của dãy tượng các tín đồ cũng tương ứng với một số nguyên tượng trưng cho nỗi khổ của chúng sinh.

Bản thiết kế được thực hiện rất công phu, mỗi bức tượng một dáng vẻ riêng, sống động và thành kính. Tuy vậy, sau khi xem nhà sư trụ trì có ý kiến:

- A di đà phật, Bần tăng muốn khi đọc từ dưới lên số thể hiện nỗi khổ của chúng sinh phải nhỏ nhất nhưng vẫn lớn hơn số thể hiện lượng từ bi của Đức Phật ở mỗi dãy, nhưng khi đứng từ trên xuống các phật tử phải thấy được rằng lượng từ bi của Đức Phật ở mỗi dãy đều lớn hơn nỗi khổ chúng sinh. Bần tăng cũng không muốn làm lại tượng, cũng không muốn làm phiền các vị cao tăng mà chỉ muốn thay đổi chỗ đặt tượng các tín đồ. Các thí chủ có thể làm điều đó giúp nhà chùa được hay không? A di đà phật.

Ví dụ, gọi các số thể hiện lượng từ bi là A và B, số thể hiện nỗi khổ chúng sinh là C và trên bảng thiết kế hiện tại A = 342876115, B = 468862513, C = 992125619. Để thỏa mãn điều kiện của nhà sư trụ trì, các tượng tín đồ cần được đổi chỗ để thể hiện số 511269992 bởi vì khi đó ta có:

• 511269992 > 342876115; 511269992 > 468862513;
• 299962115 < 511678243; 299962115 < 315268864.

Yêu cầu: Cho các số nguyên A, B, C, mỗi số có n chữ số. A và B bắt đầu bởi chữ số khác 0, còn C có thể được bắt đầu bằng một hay nhiều chữ số 0. Hãy xác định xem có cách đổi chỗ các chữ số trong C để nhận được số mới thỏa mãn điều kiện của nhà sư trụ trì đã nêu hay không. Hãy đưa ra số mới, nếu có cách đổi chỗ hoặc đưa ra -1 trong trường hợp ngược lại.

Dữ liệu

Dòng đầu tiên chứa số nguyên n ( 2 ≤ n ≤ 200000 ); Dòng thứ hai chứa số nguyên A; Dòng thứ ba chứa số nguyên B; Dòng thứ tư chứa số nguyên C.

Kết quả

• Một dòng chứa số mới nhận được từ C hoặc -1 trong trường hợp vô nghiệm.

Ví dụ

Dữ liệu
Kết quả


9
342876115
468862513
992125619
511269992

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 2 ≤ n ≤ 10.