흥미진진한 메뉴

식당에 $N$개의 메뉴가 있고, 각 메뉴는 문자열 $S^1, \dots , S^N$로 주어진다. 각 문자열 $S^i$에는 같은 길이의 기쁨 수치 배열 $A^i$가 대응된다. 이 문제에서는 세 정수 $(i, j, k)$로 정의되는 서브메뉴를 고른다. $i$는 메뉴의 번호이고, $j, k$는 고른 메뉴에서 부분 문자열을 지정한다.

품질 $Q$가 다음과 같이 정의될 때, 품질이 가장 높은 서브메뉴를 찾아야 한다.

$Q(i, j, k) = \text{popularity}(S^i_{j,k}) \cdot A^i_k \cdot |S^i_{j,k}|$

• $S^i_{j,k}$ = 문자열 $S^i$의 부분 문자열 $[j, k]$ (단, $j, k$는 1부터 시작하며 양 끝을 포함한다).
• popularity($S^i_{j,k}$) = $S^1, \dots , S^N$ 가운데 서브메뉴 문자열 $S^i_{j,k}$를 접두사로 포함하는 메뉴의 수.
• $|S^i_{j,k}|$는 서브메뉴의 크기, 즉 서브메뉴를 나타내는 부분 문자열의 길이이다.
• $A^i_k$는 서브메뉴의 기쁨 수치이며, $i$번째 배열의 $k$번째 원소이다. 여기서 인덱스 $j$는 사용되지 않는다.

품질이 가장 높은 서브메뉴를 찾을 수 있는가? 함수 $Q$의 최댓값을 출력하라.

첫 줄에는 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 식당의 메뉴 수 $N$ ($1 \le N \le 10^5$)이 주어진다.

이어서 $N$개의 줄이 주어지고, $i$번째 줄에는 $i$번째 메뉴를 나타내는 문자열 $S^i$가 주어진다. 모든 메뉴는 비어 있지 않은 소문자 영어 알파벳 문자열이며, 길이의 합은 테스트 케이스마다 $10^5$를 넘지 않는다.

그다음 $N$개의 줄이 주어지고, $i$번째 줄에는 배열 $A^i$가 주어진다. $A^i$의 길이는 문자열 $S^i$와 같고, $0 \le A^i_k \le 10^9$이다. 각 배열의 값은 공백으로 구분된다.

각 테스트 케이스마다 가장 좋은 서브메뉴 $(i, j, k)$에 해당하는 최대 품질 $Q$를 한 줄에 출력한다.

주어진 두 케이스의 정답에 해당하는 삼중항은 각각 $(1, 1, 5)$와 $(1, 4, 5)$이다.