Course Allocation in University

In a large university, various departments offer courses with different credit values. The university wants to assign courses to departments based on the department's capacity to handle the course credits. Each department has a specific capacity, and each course has a specific credit value. The goal is to assign one course to each department based on the following rules:

• A course can be assigned to a department if the department's capacity is divisible by the course's credit value.
• If multiple courses can be assigned to a department, assign the course with the smallest course ID.
• If no course satisfies the condition for a department, assign -1 to that department. Return a list of assigned courses, where each entry represents the course ID assigned to the corresponding department, or -1 if no suitable course exists.

Input Format

• The first line contains an integer D, representing the number of departments.
• The second line contains D integers, representing the capacities of the departments.
• The third line contains an integer C, representing the number of courses.
• The fourth line contains C integers, representing the credit values of the courses.

Constraints

• 1 <= D <= 10^5
• 1 <= C <= 10^5
• 1 <= department_capacity <= 10^5
• 1 <= course_credit <= 10^5

Output Format

A list of integers, where each integer represents the course ID assigned to the corresponding department, or -1 if no suitable course exists.

Examples

Input 1:

5
8 4 3 2 4
2
4 2

Output 1:

0 0 -1 1 0

Input 2:

4
2 3 5 7
3
5 3 3

Output 2:

-1 1 0 -1

Input 3:

4
10 21 30 41
2
2 1

Output 3:

0 1 0 1