난장이가 쌓아 올린 작은 성

길거리에 $N$개의 성이 일렬로 서 있다. 현재 $i$번째 성의 높이는 양의 정수 $H_i$이다.

난장이는 각 성의 높이를 양의 정수 범위에서 원하는 만큼 바꿀 수 있다. $i$번째 성의 높이를 $1$만큼 높이는 데에는 $A_i$, $1$만큼 낮추는 데에는 $B_i$의 비용이 든다.

변경한 뒤의 높이를 $H'_i$라 하자. 모든 $1 \leq i < N$에 대하여

을 만족하면 성들이 조화롭다고 한다. 성들을 조화롭게 만드는 데 필요한 최소 비용을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 최소 비용을 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $1 \leq T \leq 100$
• $1 \leq N \leq 200\,000$
• $1\le H_i,A_i,$ ()