Cho \(n\) thùng nước xếp cạnh nhau, ban đầu mỗi thùng sẽ có một lượng \(a_i\) \((1 \le i \le n)\) đơn vị nước nhất định. Trong mỗi bước, Tade sẽ múc một lượng \(x\) nước từ thùng thứ \(i\) để dùng cho sinh hoạt hằng ngày.

Tuy nhiên, vì mỗi lần múc nước Tade sẽ chọn một thùng ngẫu nhiên nên sẽ có thùng hết nhanh hơn những thùng khác. Các bạn hãy xác định thứ tự hết nước của các thùng nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \le n \le 100)\) - số thùng nước.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\).
• Dòng tiếp theo chứa một số nguyên dương \(q\) \((1 \le q \le 10^5)\) - số thao tác múc nước.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, x\) \((1 \le i \le n, 1 \le x \le a_i)\).

Output

• In ra thứ tự hết nước của \(n\) thùng từ hết đầu tiên tới hết sau cùng. Dữ liệu đảm bảo tất cả \(n\) thùng đều sẽ trống sau \(q\) thao tác.

Example

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

3 1 2