Bộ nhớ đệm LRU

Một máy chủ lưu trữ $n$ đoạn video, tất cả có cùng kích thước. Máy chủ dùng một bộ nhớ đệm (cache) áp dụng thuật toán LRU (Least Recently Used): cache chứa tối đa $k$ video và ban đầu rỗng.

Mỗi khi một video được truy vấn:

• Nếu video đã có trong cache thì giữ nguyên (chỉ cập nhật thời điểm truy vấn gần nhất của nó).
• Nếu chưa có, video được đưa vào cache. Nếu sau đó cache chứa nhiều hơn $k$ video, video ít được dùng gần đây nhất (video có thời điểm truy vấn gần nhất là sớm nhất) sẽ bị loại bỏ.

Mỗi lần một người dùng truy cập máy chủ, họ chọn video $i$ với xác suất $p_i$, độc lập với mọi lần truy cập trước đó.

Cần tính, với mỗi video, xác suất nó nằm trong cache sau ${10}^{100}$ lần truy vấn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ — số lượng video và dung lượng cache.
• Dòng thứ hai chứa $n$ số thực $p_i$ — xác suất chọn video thứ $i$, mỗi số có không quá hai chữ số sau dấu phẩy.

Đảm bảo tổng tất cả $p_i$ bằng $1$.

Dữ liệu ra

In ra $n$ số thực, số thứ $i$ là xác suất video thứ $i$ nằm trong cache sau ${10}^{100}$ lần truy vấn.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le k\le n\le 20$
• $0\le p_i\le 1$, tổng $p_i=1$

Ví dụ