Loud and Rich

There is a group of n people labeled from 0 to n - 1, each with a different amount of money and a different level of quietness.

You are given an array richer where richer[i] = [a_i, b_i] indicates that person a_i has strictly more money than person b_i.

You are also given an integer array quiet where quiet[i] is the quietness of the i-th person. All values in quiet are unique.

For each person x, find the quietest person (the person y with the smallest quiet[y]) among all people who are at least as rich as person x (including person x themselves).

Return an integer array answer where answer[x] = y.

Examples

Example 1

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]

Output: [5,5,2,5,4,5,6,7]

Explanation:

• answer[0] = 5: Among people richer than or equal to person 0 (persons 0, 1, 2, 3, 4, 5, 6), person 5 has quietness 1 which is the minimum.
• answer[7] = 7: No one is richer than person 7, so the answer is person 7 themselves with quietness 0.

Example 2

Input: richer = [[0,1],[1,2]], quiet = [0,1,2]

Output: [0,0,0]

Explanation: Person 0 is the richest and also the quietest. Everyone has person 0 as at least as rich, so all answers are 0.

Constraints

• n == quiet.length
• 1 <= n <= 500
• 0 <= quiet[i] < n
• All values of quiet are unique.
• 0 <= richer.length <= n * (n - 1) / 2
• 0 <= a_i, b_i < n
• a_i != b_i
• No two entries in richer are the same.
• The richer relations can be represented as a DAG.