You are given 3 qubits which are guaranteed to be in one of the two states:

• $|\psi_0\rangle = \frac{1}{\sqrt{3}} \big( |100\rangle + \omega |010\rangle + \omega^2|001\rangle \big)$, or
• $|\psi_1\rangle = \frac{1}{\sqrt{3}} \big( |100\rangle + \omega^2 |010\rangle + \omega|001\rangle \big)$, where $\omega = e^{2i\pi/3}$.

Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was $|\psi_0\rangle$ state or 1 if it was $|\psi_1\rangle $ state. The state of the qubits after the operations does not matter.

You have to implement an operation which takes an array of 3 qubits as an input and returns an integer. Your code should have the following signature:

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
operation Solve (qs : Qubit[]) : Int {
    // your code here
}

}