Dãy Mới

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Pypy 2 3.0s
Pypy 3 3.0s
Python 3.0s
Bộ nhớ:
Pypy 2 512M
Pypy 3 512M
Python 512M
Tác giả:
shiba
Dạng bài
Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

cho hai dãy có cùng \(n\) số nguyên dương \(a_1,a_2,...,a_n\) và \(b_1,b_2,...,b_n\).

shiba muốn tạo ra một dãy cũng có \(n\) số nguyên dương \(c_1,c_2,...,c_n\) thỏa mãn rằng \(c_k\) \((1 \le k \le n)\) là giá trị lớn nhất của \(a_i \times b_j\) với mọi \(1 \le i \le j \le k\). Hay nói một cách khác, shiba cần tạo ra một dãy thỏa mãn rằng \(c_k = max(a_i \times b_j)\) với mọi \((1 \le i \le j \le k)\).

Yêu cầu: Bạn hãy giúp shiba tạo và in ra dãy \(c\) thỏa mãn điều kiện trên.

Input

  • Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 10^6)\).
  • Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_n\) \((1 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.
  • Dòng cuối cùng chứa dãy \(b_1,b_2,...,b_n\) \((1 \le b_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

  • Gồm \(n\) dòng, dòng thứ \(i\) \((1 \le i \le n)\) in ra số \(c_i\) thỏa mãn điều kiện (\(i\) theo thứ tự tăng dần \(1,2,...,n\)).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): Có \(n \le 100\).
  • Subtask \(2\) (\(30\%\) số điểm): Có \(n \le 2 \times 10^5\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
3 2 20
1 4 1
Output 
3
12
20
Note
  • \(c_1 = max(a_1 \times b_1) = 3\).
  • \(c_2 = max(a_1 \times b_1,a_1 \times b_2,a_2 \times b_2) = 12\).
  • \(c_3 = max(a_1 \times b_1,a_1 \times b_2,a_1 \times b_3,a_2 \times b_2,a_2 \times b_3,a_3 \times b_3) = 20\).

Bình luận