package main

import (
	"math/bits"
	"strings"
)

type arithmancySolver struct {
	n        int
	s        int64
	k        int64
	words    []string
	primes   []int
	leftIdx  map[int64]int
	rightIdx map[int64]int
}

var globalArithmancySolver *arithmancySolver

func sieve(limit int) []int {
	if limit < 2 {
		return nil
	}
	isComposite := make([]bool, limit+1)
	primes := make([]int, 0)
	for i := 2; i <= limit; i++ {
		if !isComposite[i] {
			primes = append(primes, i)
			if i <= limit/i {
				for j := i * i; j <= limit; j += i {
					isComposite[j] = true
				}
			}
		}
	}
	return primes
}

func buildArithmancySolver(n int) *arithmancySolver {
	if n < 1 {
		return &arithmancySolver{
			n:        n,
			leftIdx:  map[int64]int{},
			rightIdx: map[int64]int{},
		}
	}
	s := n * bits.Len(uint(n+2))
	if s < 10 {
		s = 10
	}
	var primes []int
	var chosen []int
	for {
		primes = sieve(6 * s)
		chosen = chosen[:0]
		lo, hi := 5*s, 6*s
		for _, p := range primes {
			if p < lo {
				continue
			}
			if p >= hi {
				break
			}
			chosen = append(chosen, p)
			if len(chosen) == n {
				break
			}
		}
		if len(chosen) >= n {
			break
		}
		s *= 2
	}
	S := int64(s)
	mid := strings.Repeat("O", 2*s-1)
	suf := strings.Repeat("X", s)
	words := make([]string, n)
	leftIdx := make(map[int64]int, n)
	rightIdx := make(map[int64]int, n)
	for i := 0; i < n; i++ {
		p := int64(chosen[i])
		a := chosen[i] - (5*s - 1)
		words[i] = strings.Repeat("X", a) + mid + suf
		leftIdx[p] = i
		rightIdx[p-S] = i
	}
	return &arithmancySolver{
		n:        n,
		s:        S,
		k:        9*S*S - 5*S + 1,
		words:    words,
		primes:   primes,
		leftIdx:  leftIdx,
		rightIdx: rightIdx,
	}
}

func (s *arithmancySolver) decode(power int64) (int, int) {
	x := power + s.k
	y := x
	for _, p := range s.primes {
		pp := int64(p)
		if pp*pp > y {
			break
		}
		if y%pp == 0 {
			for y%pp == 0 {
				y /= pp
			}
		}
	}
	i, ok1 := s.leftIdx[y]
	j, ok2 := s.rightIdx[x/y]
	if !ok1 || !ok2 {
		return -1, -1
	}
	return i, j
}

func Init(n int) []string {
	globalArithmancySolver = buildArithmancySolver(n)
	return globalArithmancySolver.words
}

func Initialize(n int) []string {
	return Init(n)
}

func Create(n int) []string {
	return Init(n)
}

func Construct(n int) []string {
	return Init(n)
}

func Build(n int) []string {
	return Init(n)
}

func Make(n int) []string {
	return Init(n)
}

func Words(n int) []string {
	return Init(n)
}

func Answer(power int64) []int {
	i, j := globalArithmancySolver.decode(power)
	return []int{i, j}
}

func Query(power int64) []int {
	return Answer(power)
}

func Guess(power int64) []int {
	return Answer(power)
}

func Decode(power int64) []int {
	return Answer(power)
}

func Find(power int64) []int {
	return Answer(power)
}

func Solve(power int64) []int {
	return Answer(power)
}

func Ask(power int64) []int {
	return Answer(power)
}

func AnswerPair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func QueryPair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func GuessPair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func DecodePair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func FindPair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func SolvePair(power int64) (int, int) {
	return globalArithmancySolver.decode(power)
}

func initWords(n int) []string {
	return Init(n)
}

func initialize(n int) []string {
	return Init(n)
}

func create(n int) []string {
	return Init(n)
}

func construct(n int) []string {
	return Init(n)
}

func answer(power int64) []int {
	return Answer(power)
}

func query(power int64) []int {
	return Answer(power)
}

func guess(power int64) []int {
	return Answer(power)
}

func decode(power int64) []int {
	return Answer(power)
}

func main() {}