# i am YES going to do von neumann

class Natural(frozenset):
    def decr(self):
        #if self === Natural(): raise ValueError()
        return max(self)

    def succ(self):
        return Natural(self | {self})

    def plus(self, other):
        smother = Natural(self)
        for s in other:
            smother = smother.succ()
        return smother

    def minu(self, other):
        #if self < other: raise ValueError()
        amother = Natural(self)
        for s in other:
            amother = amother.decr()
        return amother

    def mult(self, other):
        product = Natural()
        for s in other:
            product = self.plus(product)
        return product

    def modu(self, other):
        brother = Natural(other)
        while self <= brother:
            brother = brother.minu(self)
        return brother


Zero = Natural()
One = Zero.succ()


class ChessBoard:
    # 0 1 2
    # 3 4 5
    # 6 7 8
    def __init__(self, size):
        self.taken = set()
        self.size = size
        self.rows = { # --
            map(s.mult(size).plus, {
                z
                for z in size
            })
            for s in size
        }
        self.cols = { # ||
            map(s.plus, {
                size.mult(z)
                for z in size
            })
            for s in size
        }
        self.fdia = { # \\
            map(head.plus, {
                size.succ().mult(s)
                for s in size.minu(head)
            })
            if head < size else
            map(head.minu(size).succ().mult(size).plus, {
                size.succ().mult(s)
                for s in size.plus(size).minu(head).decr()
            })
            for head in size.plus(size).decr()
        }
        self.bdia = { # //
            map(tail.plus, {
                size.decr().mult(s)
                for s in tail.succ()
            })
            if tail < size else
            map(tail.minu(size).succ().succ().mult(size).decr().plus, {
                size.decr().mult(s)
                for s in size.plus(size).minu(tail).decr()
            })
            for tail in size.plus(size).decr()
        }

    def check(self, spot):
        return (spot in self.taken)

    def queen(self, spot):
        if self.check(spot): raise #😳
        for direction in {frozenset(self.rows), frozenset(self.cols),
                          frozenset(self.fdia), frozenset(self.bdia)}:
            for line in direction:
                if spot in line:
                    for square in line:
                        self.taken.add(square)


# pretty much all of that was unnecessary but fun :3

def entry(N):
    if N < One.succ().succ().succ(): return One

    Two = One.succ()
    Three = Two.succ()
    Six = Three.mult(Two)

    # Hoffman, E.J., Loessi, J.C. and Moore, R.C. (1969): Constructions for
    # the Solution of the m Queens Problem, Mathematics Magazine, p. 66-72.
    form = Six.modu(N)
    answers = set()
    row = Zero

    if form == Two:
        temp = Two
        while temp <= N:
            answers.add(row.mult(N).plus(temp))
            temp = temp.plus(Two)
            row = row.succ()
        answers.add(row.mult(N).plus(Three))
        answers.add(row.succ().mult(N).succ())
        row = row.plus(Two)
        if Six.decr() < N:
            temp = Six.succ()
            while temp < N:
                answers.add(row.mult(N).plus(temp))
                temp = temp.plus(Two)
                row = row.succ()
            answers.add(row.mult(N).plus(Six).decr())
    elif form == Three:
        temp = Three.succ()
        while temp < N:
            answers.add(row.mult(N).plus(temp))
            temp = temp.plus(Two)
            row = row.succ()
        answers.add(row.mult(N).plus(Two))
        temp = Six.decr()
        while temp <= N:
            row = row.succ()
            answers.add(row.mult(N).plus(temp))
            temp = temp.plus(Two)
        answers.add(row.succ().mult(N).succ())
        answers.add(row.plus(Two).mult(N).plus(Three))
    else:
        temp = Two
        while temp <= N:
            answers.add(row.mult(N).plus(temp))
            temp = temp.plus(Two)
            row = row.succ()
        temp = One
        while temp <= N:
            answers.add(row.mult(N).plus(temp))
            temp = temp.plus(Two)
            row = row.succ()

    nqueens = Zero
    for p in answers: # for fun, print len p
        nqueens = nqueens.succ()
    if nqueens != N:
        raise #😳

    yuri_pile = ChessBoard(N)
    for p in answers: # honestly don't do this it slows everything
        yuri_pile.queen(p.decr())

    return answers