Under construction

Still being built. Things may change

Course Basket

Interview

Time limit2sMemory limit256 MB

Summary
Given seat caps and two rounds of course requests per student, decide which courses each student gets, breaking ties by student order within each round.
Level

Medium5 of 10

Topics
Implementation, Simulation, Greedy, Sorting
Solved
No attempts yet

Problem

Students at Konkuk University can pre-register for courses through the course basket before the official registration period. As in official registration, each course has a fixed enrollment cap in the course basket.

The course basket runs in two rounds. During the course basket period, students can add the courses they want to their own course basket.

When the first round ends, enrollment is finalized for each course as long as the enrollment cap is not exceeded. The enrollment cap for the second round is the number of seats left after the first round's enrollment is finalized. When the course basket ends, each student's course basket is not reset.

Given N students participating in the course basket for M courses, along with the courses each student put in the first and second rounds, print for each student the courses they successfully enrolled in through the course basket.

Input

The first line gives two natural numbers N and M separated by a space. They are the number of students and the number of courses.

The second line gives the enrollment cap of each course L1, L2, ..., LM separated by spaces.

Over 2×N lines, the course basket request queries are given. The first N lines give the courses that student 1, student 2, …, student N put in the first round, and the following N lines give the courses put in the second round.

Each request query ends with -1, and no student adds the same course twice.

Output

From the first line over N lines, print the courses student 1 successfully enrolled in, the courses student 2 successfully enrolled in, …, the courses student N successfully enrolled in, separated by spaces and in ascending order. If a student enrolled in no courses, print “망했어요” (without the quotes) instead.

Constraints

  • 1 ≤ N, M ≤ 1,000
  • 1 ≤ Li ≤ 1,000 for all i with 1 ≤ i ≤ M

Examples1

  1. Example 1

    Input
    3 5
2 1 3 1 2
1 2 3 -1
1 2 -1
-1
4 5 -1
4 -1
1 2 4 -1
    Expected output
    1 3 5
1
망했어요