은행원

에덱(Edek)은 은행 창구에서 고객 계좌의 입금과 출금을 처리하는 일을 합니다. 이 일이 때때로 지루해서, 에덱은 입금과 출금을 처리하는 자신만의 방식을 고안했습니다.

하루를 시작할 때 에덱의 금고에는 출금에 사용할 수 있는 금액 $S$가 들어 있습니다. 고객이 계좌에 돈을 입금하러 오면, 에덱은 입금액을 시스템에 기록하고 받은 현금(고객은 항상 정확한 금액을 가져옵니다)을 봉투에 넣어 이전 입금 봉투들이 쌓인 더미의 맨 위에 올려 둡니다.

고객이 금액 $X$를 출금하러 오면, 에덱은 다음과 같이 처리합니다.

• 더미에 봉투가 하나도 없으면, 금고에서 돈을 지급합니다.
• 출금 금액 $X$가 더미에 있는 봉투들의 금액 중 가장 작은 값보다 작으면, 에덱은 $X$ 전액을 금고에서 지급합니다.
• 그 외의 경우에는, 전액이 지급될 때까지 더미의 맨 위 봉투를 하나씩 꺼내어 부족한 금액에 사용합니다. 전액을 지급한 뒤 마지막으로 꺼낸 봉투에 돈이 남으면, 그 남은 돈은 금고에 넣습니다. 봉투를 모두 꺼냈는데도 고객이 전액을 받지 못했다면, 나머지 금액은 금고에서 지급합니다.

금고에는 필요한 작업을 수행하기에 충분한 돈이 항상 들어 있다고 가정해도 됩니다.

은행 시스템이므로 에덱은 실수를 하고 싶지 않습니다. 모든 고객의 입금과 출금을 처리한 뒤 금고에 있어야 할 금액과 더미에 남은 봉투들에 들어 있는 금액을 계산하는 프로그램을 작성해 에덱을 도와주세요.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 3$)가 주어집니다. 이어서 각 테스트 케이스가 주어집니다.

각 테스트 케이스는 모든 고객 행동의 기록입니다. 첫째 줄에는 두 정수 $n$ ($1 \le n \le 10^6$)과 $S$ ($1 \le S \le 10^{12}$)가 주어지며, 각각 고객 행동의 수와 하루를 시작할 때 금고에 들어 있던 금액을 뜻합니다. 다음 $n$개의 줄에는 각 고객 행동이 하나의 정수 $x$ ($-10^6 \le x \le 10^6$, $x \neq 0$)로 주어집니다. 양수는 계좌로의 입금, 음수는 계좌에서의 출금을 뜻합니다.

행동을 처리하는 동안 금고에 들어 있는 금액이 $10^{12}$을 넘는 경우는 없다고 가정해도 됩니다.

각 테스트 케이스마다, 공백 하나로 구분된 두 정수를 한 줄에 출력합니다. 각각 모든 고객 행동을 처리한 뒤 금고에 남은 금액과, 더미에 남은 봉투들에 들어 있는 금액의 합입니다.