Description

You have $n$ weights, each of which is $1$ gram, $2$ grams, or $3$ grams. You do not know the exact mass of each weight, but you know some pairwise weight comparisons. You place two weights $A$ and $B$ on the left pan of a balance scale, and you need to choose two other weights to place on the right pan. How many unordered choices are there that make the left pan heavier ($c_1$), balance ($c_2$), or the right pan heavier ($c_3$)? (Only count choices for which the outcome is uniquely determined.) The choice is unordered; that is, choosing weights $1$ and $2$ is the same as choosing $2$ and $1$.

Input Format

The first line contains three positive integers $n,A,B$ ($1\le A,B\le n,A\neq B$).

The following $n$ lines contain the weight relation matrix. In row $i$, the $j$-th character is a plus + if weight $i$ is heavier than weight $j$, a minus - if weight $i$ is lighter than weight $j$, an equals = if weight $i$ and weight $j$ are equal, and a question mark ? if their relation is unknown.

It is guaranteed that there exists at least one configuration consistent with this matrix.

Output Format

Output a single line containing three integers: $c_1,c_2,c_3$.

6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?

1 4 1

14 8 4
?+???++?????++
-??=?=???????=
??????????=???
?=??+?==??????
???-???-???-??
-=????????????
-??=???=?-+???
???=+?=???????
??????????????
??????+???????
??=???-????-??
????+?????+???
-?????????????
-=????????????

18 12 11

Hint

Constraints: $4\le n\le 50$.

Translated by ChatGPT 5