노크한 과수원은 똑똑한 과수원이다

루루는 과수원의 효율을 높이기 위해 자동 사과 포장 라인을 도입했다.

루루가 하루 작업 시간을 양의 정수 $T$분으로 정했을 때, 과수원 전체에서 정확히 $T$상자의 사과가 수확되어야 포장 라인이 안정적으로 작동한다.

과수원에는 $N$개의 수확반이 있다. 수확반 $i$에는 네 정수 $L_i$, $R_i$, , 가 정해져 있다.

작업 시간 $T$가 주어지면, $L_i\le T\le R_i$를 만족하는 수확반만 작업에 투입된다. 투입된 수확반의 수를 $$라 하자.

투입된 수확반 $i$는 작업을 시작할 때 $C_i$상자의 사과를 수확한다. 이후 원래는 $D_i$분마다 사과 한 상자를 추가로 수확할 수 있지만, 투입된 $K$개의 수확반이 통로와 장비를 공유하므로 작업 효율이 배로 감소한다.

따라서 수확반 $i$가 사과 한 상자를 추가로 수확하는 데에는 $K\cdot D_i$분이 필요하며, $T$분 동안 추가로 수확하는 사과 상자의 수는

$\left\lfloor\frac{T}{K\cdot D_i}\right\rfloor$

이다.

그러므로 작업 시간 $T$에 수확되는 사과의 총량은

$\sum_{\substack{1\le i\le N\\L_i\le T\le R_i}} \left(C_i+\left\lfloor\frac{T}{K\cdot D_i}\right\rfloor\right)$

이다. 투입되는 수확반이 없다면 총수확량은 $0$이다.

총수확량이 정확히 $T$가 되는 모든 양의 정수 $T$의 개수와, 그러한 $T$ 중 최댓값을 구하여라.

첫째 줄에 테스트 케이스의 수 $Q$가 주어진다. ($1\le Q\le1\,000$)

각 테스트 케이스의 첫째 줄에 수확반의 수 $N$이 주어진다. ($1\le N\le300\,000$)

각 테스트 케이스마다 조건을 만족하는 양의 정수 $T$의 개수와, 그러한 $T$ 중 최댓값을 공백으로 구분하여 출력한다.

조건을 만족하는 $T$가 존재하지 않는다면 0 -1을 출력한다.