Nhân dịp kết thúc năm học, Bảo Bay Bổng và gia đình sẽ đi du lịch tại đất nước A. Cậu được bố mẹ giao cho công việc lên kế hoạch cho chuyến đi. Đất nước A có n điểm tham quan được đánh số từ 1 tới n, điểm tham quan thứ i có toạ độ (~ x_i, y_i ~), được kết nối với nhau bằng những con đường một chiều. Vì địa hình đặc thù nên chính phủ chỉ xây đường đi từ điểm tham quan thứ i tới điểm tham quan thứ j nếu như ~ x_i > x_j ~ và ~ y_i < y_j ~ . Để chuẩn bị kĩ lưỡng cho chuyến đi, cậu muốn tìm hiểu xem với mỗi số nguyên dương l (1 ≤ l ≤ n), có bao nhiêu hành trình tham quan đi theo những đường đi có sẵn mà đi qua đúng l điểm tham quan. Hãy giúp Bảo Bay Bổng nghiên cứu vấn đề này.

Lấy kết quả theo modulo ~ 10^9 ~ + 7.

Input

• Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 2000) — số điểm tham quan.
• Dòng thứ hai chứa n số nguyên ~ x_1, x_2, . . . , x_n ~ (~ 0 ≤ |x_i| ≤ 10^9 ~) — hoành độ của các điểm tham quan.
• Dòng thứ ba chứa n số nguyên ~ y1, y2, . . . , yn ~ (~ 0 ≤ |y_i| ≤ 10^9 ~) — tung độ của các điểm tham quan.

Output

• In ra trên một dòng n số nguyên không âm, số thứ i là số hành trình đi qua đúng i điểm tham quan, tính theo modulo ~ 10^9 ~ + 7.

Sample

Input #1

6
3 2 6 4 5 1
5 5 6 2 1 4

Output #1

6 7 3 0 0 0

Problem source: Free Contest 126