solution

Biến ngẫu nhiên rời rạc $X$ được cho bởi bảng gồm $n$ cặp $(x_i, p_i)$, trong đó các $x_i$ là số nguyên đôi một phân biệt (không nhất thiết cho theo thứ tự tăng dần trong dữ liệu vào), và $\sum_i p_i = 1$ (đề bài đảm bảo, không cần kiểm tra).

Hàm phân phối tích lũy (CDF) của $X$ được định nghĩa là $F(t) = P(X \le t) = \sum_{i:\, x_i \le t} p_i, \quad t \in \mathbb{R}.$

Cho $q$ truy vấn, mỗi truy vấn là một số thực $t_j$, hãy tính $F(t_j)$.

Ví dụ: $X \in \{1,2,3\}$ với $p=(0.2,0.3,0.5)$ (cho theo thứ tự bất kỳ trong input). Với $t=1.5$: $F(1.5) = 0.2$ (chỉ $x=1 \le 1.5$). Với $t=3$: $F(3)=1.0$.

Input:

3
1 0.2
3 0.5
2 0.3
2
1.5
3

Output:

0.2000
1.0000