Farmer John 농장은 헛간 $N$개 ($2\le N\le2\cdot10^5$), 번호 $1\ldots N$과 두 헛간을 잇는 길 $N-1$개가 있다. 어디서든 다른 헛간으로 간다. 헛간 $j$에는 건초 $h_j$묶음 ($1\le h_j\le10^9$)이 있다.

소를 기쁘게 하려 건초를 옮겨 모든 헛간의 수를 같게 한다. 길로 연결된 둘을 골라 첫 헛간의 현재 수 이하인 양의 정수 묶음을 첫째에서 둘째로 옮기도록 일꾼에게 명령한다.

최소 명령 수로 끝내는 목록을 정하자. 존재가 보장된다.

입력

첫 줄 $N$.

둘째 줄은 공백 구분 $h_j$, $j=1\ldots N$.

마지막 $N-1$줄은 공백 구분 번호 $u_i,v_i$, 둘을 잇는 양방향 길이다.

출력

최소 명령 수와 그 길이의 목록을 한 줄에 하나씩 출력한다.

명령은 공백 구분 양의 정수 셋, 출발 헛간, 도착 헛간, 옮기는 묶음 수다.

여러 해면 아무거나 출력한다.

예제

입력 1

4
2 1 4 5
1 2
2 3
2 4

출력 1

3
3 2 1
4 2 2
2 1 1

참고

$12$묶음과 $4$헛간이라 끝에 각 $3$이다. 명령은 다음과 같다.

1. $3$에서 $2$로 $1$묶음.

2. $4$에서 $2$로 $2$묶음.

3. $2$에서 $1$로 $1$묶음.

서브태스크

• 테스트 $2\ldots8$: $N\le5000$.

• 테스트 $7\ldots10$: $v_i=u_i+1$.

• 테스트 $11\ldots16$: 추가 제한 없음.

문제 출제: Aryansh Shrivastava