#P12336. 第三心脏

第三心脏

题目背景

第三心脏

题目描述

mikage 喜欢构造题,这天她想到了一个简单的构造题:

给定 aa 试构造正整数四元组 (a,b,c,d)(a,b,c,d) 满足:

  1. a2+b2+c2+d2=abcd\sqrt{a^2+b^2+c^2+d^2}=a\oplus b\oplus c\oplus d

  2. a<b<c<d<263a<b<c<d<2^{63}

无解输出 1-1\oplus 是二进制按位异或。

输入格式

一行,一个整数 aa

输出格式

如果有解,一行三个整数 b,c,db,c,d 带空格输出。无解输出 1-1

31
172 484 632

提示

样例解释

依题面得。

数据范围

本题开启数据捆绑,你只有通过了一个 Subtask 内所有的测试点才能获取该 Subtask 的分数。

Subtask aa 的范围 特殊性质 分数
0 a10a\le 10 5
1 a300a\le 300
2 a4×103a\le 4\times 10^3 A 10
3 a107a\le 10^7 B
4 a2×108a\le 2\times 10^8 C 20
5 a109a\le 10^9 D 10
6 40

对于所有数据有 1a1091\le a \le 10^9

特殊性质 A:存在大于等于 22 的整数 kk 满足 a=2ka = 2^k

特殊性质 B:a0(mod4)a \equiv 0 \pmod{4}

特殊性质 C:a1(mod4)a \equiv 1 \pmod{4}

特殊性质 D:存在大于等于 22 的整数 kk 满足 a=2k1a = 2^k-1