Note: Giới hạn thời gian là 5s. Giới hạn bộ nhớ là 512MB.

Bessie dạo này có một sự thích thú với ma thuật và cô bò đang thu thập mana cho một câu thần chú rất quan trọng. Bessie có \(N\) \((1 \le N \le 18)\) bể mana. Bể thứ \(i\) tích tụ được \(m_i\) mana mỗi giây \((1 \le m_i \le 10^8)\). Có \(M\) con đường giữa các bể mana này \((0 \le M \le N(N - 1))\), các đường đi này là một chiều, đường thứ \(i\) nối từ bể \(a_i\) sang bể \(b_i\), Bessie mất \(t_i\) giây để đi qua con đường này (\(1 \le a_i, b_i \le N\), \(a_i \ne b_i\), \(1 \le t_i \le 10^9\), mỗi cặp \((a_i, b_i)\) xuất hiện nhiều nhất một lần). Khi Bessie ở bể mana nào đó, cô nàng có thể lấy hết mana ở bể này và khiến nó trống không. Tại thời điểm \(0\), mọi bể mana đều trống không và cô nàng có thể bất kì bể nào để bắt đầu.

Hãy trả lời \(Q\) truy vấn \((1 \le Q \le 2 \times 10^5)\), mỗi truy vấn gồm \(2\) số nguyên là \(s\) và \(e\) \((1 \le s \le 10^9, 1 \le e \le N)\), bạn cần cho biết lượng mana lớn nhất cô nàng có thể thu thập được và ở giây thứ \(s\), cô nàng phải ở bể \(e\).

Input

• Dòng đầu là số \(N\) và \(M\).
• Dòng thứ hai là các số \(m_1, m_2, ..., m_N\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) là bộ ba số \((a_i, b_i, t_i)\).
• Dòng tiếp theo là số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng là hai số nguyên \(s\) và \(e\) thể hiện một truy vấn.

Output

• \(Q\) dòng là đáp án của các truy vấn.

Scoring

• Subtask \(1\): \(N \le 10, Q \le 100\).
• Subtask \(2\): \(N \le 10\).
• Subtask \(3\): \(Q \le 100\).
• Subtask \(4\): \(N = 16\).
• Subtask \(5\): \(N = 17\).
• Subtask \(6\): Không có ràng buộc gì thêm.

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

5
50
100
1090

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

160000000
239999988050000000
119992550000000