Tháng 7 năm 2023, lần đầu tiên Hiếu được tham dự cuộc thi học sinh giỏi Duyên hải và Đồng bằng Bắc Bộ năm 2023 tại tỉnh Thái Nguyên. Lần đầu tiên được đi thi xa nhà cậu được bố mẹ giao cho công việc chuẩn bị và lên kế hoạch cho chuyến đi. Hiếu rất hào hứng và tìm hiểu các thông tin về tỉnh Thái Nguyên để sau kì thi bổ ích Hiếu có một chuyến tham quan bổ ích.

Tỉnh Thái Nguyên, là một trong những trung tâm chính trị, kinh tế của khu Việt Bắc nói riêng, của vùng trung du miền núi Đông Bắc nói chung, là cửa ngõ giao lưu kinh tế xã hội giữa vùng trung du miền núi với vùng đồng bằng Bắc Bộ; phía Bắc tiếp giáp với tỉnh Bắc Kạn, phía Tây giáp với các tỉnh Vĩnh Phúc, Tuyên Quang, phía Đông giáp với các tỉnh Lạng Sơn, Bắc Giang và phía Nam tiếp giáp với thủ đô Hà Nội; diện tích tự nhiên ~3.562,82~ km².

Tỉnh Thái Nguyên có ~n~ điểm tham quan được đánh số từ ~1~ tới ~n~, điểm tham quan thứ ~i~ có tọa độ ~(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 \le l \le 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.

Các bạn lập trình viên hãy giúp Hiếu nghiên cứu vấn đề này nhé. 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 \le n \le 2000)~ - số điểm tham quan.

• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \dots, x_n~ ~(0 \le |x_i| \le 10^9)~ là hoành độ của các điểm tham quan.

• Dòng thứ ba chứa ~n~ số nguyên ~y_1, y_2, \dots, y_n~ ~(0 \le |y_i| \le 10^9)~ là tung độ của các điểm tham quan.

Output

Ghi ra 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~.

Scoring

Sample Input 1

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

Sample Output 1

6 7 3 0 0 0

Notes

• Các hành trình gồm ~1~ điểm tham quan: ~(1)~; ~(2)~; ~(3)~; ~(4)~; ~(5)~; ~(6)~.

• Các hành trình gồm ~2~ điểm tham quan: ~(4,1)~; ~(4,2)~; ~(4,6)~; ~(5,1)~; ~(5,2)~; ~(5,4)~; ~(5,6)~.

• Các hành trình gồm ~3~ điểm tham quan: ~(5,4,2)~; ~(5,4,6)~; ~(5,4,1)~.

• Không có hành trình thỏa mãn đi qua ~4~, ~5~ hoặc ~6~ điểm tham quan.