You are given N qubits (1 ≤ N ≤ 8) in zero state $\text{[math]}$ . Your task is to create Greenberger–Horne–Zeilinger (GHZ) state on them:

$\text{[math]}$

Note that for N = 1 and N = 2 GHZ state becomes states $\text{[math]}$ and $\text{[math]}$ from the previous tasks, respectively.

Input

You have to implement an operation which takes an array of N qubits as an input and has no output. The "output" of your solution is the state in which it left the input qubits.

Your code should have the following signature:

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[]) : ()
    {
        body
        {
            // your code here
        }
    }
}

Generate GHZ state