. Consider the situation where $$$x^2 \equiv y^2 \pmod{p}$$$, this is equivalent to saying that $$$x^2 - y^2 \equiv 0 \pmod{p}$$$. Using the difference-of-squares formula, we get $$$(x - y) \cdot (x + y) \equiv 0 \pmod{p}$$$. It follows that either $$$x - y \equiv 0 \pmod{p}$$$ or $$$x + y \equiv 0 \pmod{p}$$$, that is, either $$$x \equiv y \pmod{p}$$$ or $$$x \equiv -y \pmod{p}$$$.

It turns out that all numbers split into pairs $$$x$$$ and $$$-x$$$, so each quadratic residue has exactly $$$2$$$ roots, with each number being the root of some quadratic residue $$$\implies$$$ number of quadratic residues exactly $$$\frac{p - 1}{2}$$$ $$$\implies$$$ number of quadratic nonresidues $$$p - 1 - \frac{p - 1}{2} = \frac{p - 1}{2}$$$.

Let $$$x$$$ and $$$y$$$ be quadratic residues, let $$$a^2 \equiv x \pmod{p}$$$ and $$$b^2 \equiv y \pmod{p}$$$. Then $$$(ab)^2 \equiv xy \pmod{p}$$$.

Let $$$x$$$ be a quadratic nonresidue and $$$y$$$ be a quadratic residue, let's prove that $$$\frac{1}{y}$$$ is also a quadratic residue. Let $$$b^2 \equiv y \pmod{p}$$$, then $$$(\frac{1}{b})^2 \equiv \frac{1}{y} \pmod{p}$$$.

$$$x \cdot y \equiv z \pmod{p}$$$, suppose $$$z$$$ is a quadratic residue, then $$$x \equiv z \cdot \frac{1}{y} \pmod{p}$$$ $$$\implies$$$ $$$x$$$ is quadratic residue, since $$$z$$$ is quadratic residue and $$$\frac{1}{y}$$$ is quadratic residue. The contradiction $$$\implies$$$ $$$z$$$ is quadratic nonresidue.

Let $$$x$$$ and $$$y$$$ be quadratic nonresidues, $$$x \cdot y \equiv z \pmod{p}$$$ and $$$z$$$ a quadratic nonresidue, and $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}$$$ all quadratic residues. Consider the following set of residues $$$xa_1, xa_2, xa_3, \cdots, xa_{\frac{p - 1}{2}}, xy$$$. All numbers in this set are quadratic nonresidue, but there are $$$\frac{p + 1}{2}$$$ numbers in the set, and this is more than the quadratic nonresidue $$$\implies$$$ there are $$$2$$$ equal numbers in the set. Note that if $$$xk \equiv xl \pmod{p}$$$ and $$$x$$$ is not a multiple of $$$p$$$, then $$$k \equiv l \pmod{p}$$$. So in the set $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}, y$$$ exist equal numbers, but in this set all numbers are different ($$$a_i \ne a_j$$$ since we took different quadratic residues, and $$$y \ne a_i$$$ since $$$y$$$ is quadratic nonresidue and $$$a_i$$$ is quadratic residue). Contradiction, so $$$z$$$ is a quadratic residue.

First, let us prove that if $$$a$$$ is not divisible by $$$p$$$, then $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$. By Fermat's small theorem, $$$a^{p - 1} \equiv 1 \pmod{p}$$$, it was proved above that any quadratic residue has exactly $$$2$$$ roots, with $$$1$$$ being $$$1$$$ and $$$-1$$$. $$$(a^{\frac{p - 1}{2}})^2 = a^{p - 1}$$$ $$$\implies$$$ $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$.

Let $$$a$$$ be a quadratic residue and $$$x^2 \equiv a \pmod{p}$$$, then $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, since $$$(x^2)^{\frac{p - 1}{2}} = x^{p - 1} \equiv 1 \pmod{p}$$$, and this is true by Fermat's small theorem.

Consider the polynomial $$$x^{\frac{p - 1}{2}} - 1$$$ modulo $$$p$$$, its degree is $$$\frac{p - 1}{2}$$$ and we have already found $$$\frac{p - 1}{2}$$$ roots $$$\implies$$$ it has no more roots $$$\implies$$$ if $$$b$$$ is quadratic nonresidue, then $$$b^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

int power(int a, int x, int mod) {
    int res = 1;
    while (x != 0) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p - 1) / 2, p) == 1;
}

mt19937_64 mt(123);

int power(int a, int x, int mod) {
    int res = 1;
    while (x) {
        if (x % 2 == 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
        x /= 2;
    }
    return res;
}

bool check(int a, int p) {
    return power(a, (p - 1) / 2, p) == 1;
}

int find_i(int p) {
    if (p % 4 == 3) {
        return -1;
    }
    if (p == 2) {
        return 1;
    }
    while (true) {
        int a = mt() % (p - 1) + 1;
        if (!check(a, p)) {
            return power(a, (p - 1) / 4, p);
        }
    }
}