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
    }
}