Taja는 종종 장난감 가게에 들러 가게 진열창 근처에 있는 전자식 표지판을 보곤 했습니다. 표지판에는 두 개의 정수가 표시되어 있습니다. 가게 진열창에는 여러 종류의 장난감이 전시되어 있지만, 표지판의 숫자는 실제 남아 있는 장난감 종류의 수와 일치하지 않을 수 있습니다. 장난감을 구매한 직후에 바로 진열창에서 제거되는 것이 아니라, 구매 후 일정 시간이 지난 뒤에야 제거되기 때문입니다. 이 시간은 장난감 종류마다 다를 수 있습니다.

가게에는 $n$ 종류의 장난감이 있습니다. 각 장난감 종류에 대해 초기 개수 $c_i$와 구매 후 진열창에서 제거되기까지 걸리는 시간 $t_i$분(분 단위)이 알려져 있습니다. 매 분마다 다음 과정이 일어납니다.

• 구매한 지 해당 시간이 지난 장난감들이 진열창에서 제거됩니다.
• 전자식 표지판이 업데이트됩니다.
• 새로운 손님이 와서 재고가 남아 있는 장난감 중 하나를 반드시 구매합니다.

Taja는 항상 전자식 표지판에 적힌 숫자의 의미를 궁금해했고 최근 그 의미를 알아냈습니다. 두 숫자 모두 가게에서 구매 가능한 장난감의 종류가 몇 가지인지를 나타내지만, 첫 번째 숫자는 현재까지 재고가 남아 있을 가능성이 있는 종류의 수를 나타내고, 두 번째 숫자는 현재까지 확실하게 재고가 남아 있는 종류의 수를 나타냅니다. Taja는 이 표지판이 손님들에게 얼마나 유용한 정보인지도 궁금해합니다. 그래서 그녀는 손님들의 행동을 모델링하고 표지판을 업데이트할 프로그램이 필요합니다.

당신의 임무는 매 분마다 전자식 표지판의 숫자들을 계산하는 것입니다.

입력

첫 번째 줄에는 장난감 종류의 수를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어집니다.

이어지는 $n$개의 줄에는 각 $i$번째 장난감 종류의 초기 개수 $c_i$와 구매 후 진열창에서 제거되기까지 걸리는 시간 $t_i$ ($1 \le c_i \le 10^5, 1 \le t_i \le 100$)가 주어집니다.

다음 줄에는 손님의 수를 나타내는 정수 $k$ ($1 \le k \le 10^5$)가 주어집니다.

이어지는 $k$개의 줄에는 $i$번째 분에 제거된 장난감의 개수 $q_i$와 그 장난감들의 번호 $p_1, p_2, \dots, p_{q_i}$가 주어집니다.

출력

$k$개의 줄을 출력해야 하며, 각 줄에는 $i$번째 분이 시작되는 시점의 전자식 표지판에 표시될 두 정수 $a_i$와 $b_i$를 출력합니다.

예제

입력 1

3
1 2
2 1
3 3
6
0
0
0
3 1 2 3
0
1 2

출력 1

3 3
3 2
3 2
2 2
2 2
1 1

참고

위 예제에서 가게 진열창에는 첫 번째 종류의 장난감 1개, 두 번째 종류 2개, 세 번째 종류 3개가 있으며, 구매 후 각각 2분, 1분, 3분 뒤에 제거됩니다. 표지판의 숫자는 다음과 같은 순서로 변합니다.

• 3/3: 첫 번째 손님 이전에는 손님이 없었으므로, 어떤 장난감이든 구매할 수 있습니다.
• 3/2: 첫 번째 손님이 첫 번째 종류의 장난감을 구매했을 가능성이 있으므로, 두 번째 손님이 그것을 구매할 수 있다는 확신은 없습니다.
• 3/2: 첫 번째 종류나 두 번째 종류의 장난감이 진열창에서 제거되지 않았으므로, 이는 첫 번째 손님이 세 번째 종류의 장난감을 구매했음을 의미합니다. 두 번째 손님이 무엇을 구매했는지는 아직 결정할 수 없습니다.
• 2/2: 첫 번째 종류의 장난감이 더 이상 없습니다.
• 2/2: 진열창에서 제거된 장난감이 없으므로, 이전 손님이 세 번째 종류의 장난감을 구매했음을 의미합니다.
• 1/1: 세 번째 종류의 장난감이 하나만 남아 있습니다.