Sample Input 1

3
1
4
5

Sample Output 1

1
1
4
1 2 3 4
4
1 2 3 5

Sample Input 1

2
4 1 1
5 1 2

Sample Output 1

YES
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
NO

Sample Input 1

2
0 1 0 1
6 2 2 1 3 1 4 2 5 3 4 3 3
0 1 0 1
6 2 -1 1 0 1 1 2 2 3 1 3 0

Sample Output 1

NO
YES

Sample Input 1

5
1 2 4 4 8
5
1 2 4 8 8
0

Sample Output 1

YES
1 2 4 8 4
NO

Sample Input 1

1
7 12
2 7 1
2 3 2
5 6 3
4 5 4
6 7 5
3 4 5
1 7 6
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9

Sample Output 1

1 2

Sample Input 1

4
A
A
A
A

Sample Output 1

3

Sample Input 2

6
A
D
B
B
C
A

Sample Output 2

1

Sample Input 1

2
4
3 2 1 4
4
2 3 0 0

Sample Output 1

2
0

Sample Input 1

3
-1 2 -1
2 2
1 -1 1

Sample Output 1

1

Sample Input 2

7
-1 4 5 1 0 -1 -1
-1 3 2 0 0 1
-1 4 -1 1 0 -1 -1
1 3 4 2 2 4
0 2 3 -1 4 4 2
-1 4 4 3 3 2
1 -1 -1 -1 4 2 -1

Sample Output 2

1

Sample Input 3

3
-1 2 -1
2 2
-1 -1 -1

Sample Output 3

4

Sample Input 1

5 6
1 3 4 5
1 2 10
2 3 20
1 3 30
4 2 10
2 5 30
4 5 40
5 6
1 3 4 5
1 2 10
2 3 20
1 3 20
4 2 10
2 5 30
4 5 40
3 2
1 3 2 3
1 3 10
2 3 20
0 0

Sample Output 1

1
0
1

Sample Input 1

3
6 1
6 2
6 6

Sample Output 1

1
1
10

Sample Input 1

6
1 2
1 3
2 4
3 3
3 2
2 1

Sample Output 1

7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381

Sample Input 2

8
3 1
6 1
8 3
8 6
6 8
3 8
1 6
1 3

Sample Output 2

22.42718386376139
22.42718386376139
22.42718386376139
22.42718386376139
22.42718386376139
22.42718386376139
22.42718386376139
22.42718386376139

Sample Input 1

517 33 34 35

Sample Output 1

314