暂无测试数据。

Description

Some students have just took a test, and they are discussing it.

This test consists solely of multiple choice problems, and each student remembers his/her choice. They do not know which one is the answer.

There are $m$ problems in the test, the $i$ -th problem is of $s_i$ points. If the $i$ th problem is answered correctly, the value $a_i$ is added to to the score of the student. If it is answered incorrectly or not answered, the student’s score will not change. Your task is to give a set of correct answers and determine the maximum total score students may get.

Input

The first line of input contains a single integer $m(0 < m \le 2\cdot 10^6)$

The second line contains $m$ space separated integers $s_i(-10^3\le s_i\le 10^3)$

Then $m$ lines follow, each line contains $4$ space separated integers, $a_i,b_i,c_i,d_i(0 \le a_i,b_i,c_i,d_i \le 10^3)$denoting the number of students who have chosen the corresponding choice. It is not guranteed that the sum of each line are pairwise equal(some students may have skipped problems). Refer to the example input for better understanding.

Output

Print two lines. The first line contains a single integer $k$ -- the maximal total students get.

The second line contains a string of length $m$, it should contain only characters A,B,C and D. It should be a possible answer that yields the maximal total score $k$. If multiple answers exist, print the lexicographically smallest(see Notes section) one.

Examples

Sample Input 1

3
1 2 3
10 2 3 0
2 3 10 0
2 0 0 10

Sample Output 1

60
ACD

Notice that $10+2+3+0$ does not equal to $2+0+0+10$.

Sample Input 2

8
1 9 2 6 0 8 1 7
1 4 3 5
2 5 2 5
1 5 7 2
2 5 7 7
10 2 3 4
2 3 1 9
11 2 3 8
2 1 10 10

Sample Output 2

259
DBCCADAC

Notes

For two sequences $A$ and $B$, both of length $n$, we say $A$ is lexicographically smaller than $B$, if and only if $\exists x \in [1, n]$ so that

• For all $1\le i < x, A_i=B_i$
• $A_x < B_x$.

In this problem, the characters are compared using their ASCII number.