题面过于抽象，受笔者语文水平所限，就不在此翻译了，烦请各位读者自行理解。
探索
这是笔者第一道自己做的构造题。
我们不妨采用如下的顺序接吻：（用 C++ 语言表示）
void kiss(int Boy,int Girl){}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
kiss(i,j);其中 $Boy$ 表示男生编号，$Girl$ 表示女生编号。下面分别简称编号为 $i$ 的男生和女生为“男 $i$”和“女 $i$”。
笔者首先依次思考了 $n=3$ 和 $n=4$ 的情况，很快就想了出来。但是发现相同的方法对 $n=5$ 和 $n=6$ 的情况不适用（总是少一张纸）。因此，我重新思考了 $n=5$ 时的构造方案：
在开始安排之前，算一算，有 $\lfloor\frac{3\times 5}{2}\rfloor=7$ 张纸可以用。然后，思考亲吻的具体流程。
首先还是男 $1$ 亲遍所有女生。显然在男 $1$ 亲遍前 $(n-1)$ 个女生之前，男 $1$ 亲的那张纸的反面是不能动的。所以前 $(n-1)$ 个女生总是隔着（每次都不同）的一张纸巾和男 $1$ 接吻。如下：（蓝笔写的编号代表男生，红笔写的编号代表女生，黑笔写的编号为纸巾编号，灰线连接的两个面为接触面）
最初尝试的时候发现如果女 $n$ 直接和男 $1$ 用同一张纸亲会出问题，所以这次我们让女 $n$ 和前面 $(n-1)$ 名女生一样，也隔着一张纸巾和男 $1$ 接吻：
轮到男 $2$ 了。发现如果男 $2$ 如果直接用男 $1$ 用过的那张纸反面去亲遍女生会出大问题，让男 $2$ 新拿一张纸的话……没想过。（AC 掉这道题之后发现可以实现，只不过是顺序上的差异）所以，干脆大胆一点，直接让男 $2$ 和各位女生都只用一张纸巾亲吻！（这么说可能会引起误会，以下图所描述的情况为准）便宜男 $2$ 了
轮到男 $3$。发现男 $3$ 如果用男 $1$ 用过的那张纸反面的话会出大问题，所以要让男 $3$ 拿一张没用过的纸巾。但是……（本题解最关键的部分来了）男 $3$ 的亲法很有讲究。先用他亲的这张纸反面接触男 $1$ 亲过的那张纸反面（都是空白），然后让男 $1$ 亲过的那面与男 $2$ 亲过的那面接触，男 $2$ 亲过的那面的反面就是女生们亲的面了。
感觉没看懂？看下面这张图就明白了：
太乱了？看看这个局部图：
图中紫色的两个（空白）面相互接触，蓝灰色的两个面相互接触。这样，男 $3$ 和女生之间，就隔了 $3$ 张纸。
轮到男 $4$。男 $4$ 肯定不能拿男 $3$ 亲过的那张纸的反面去亲（男 $3$ 的细菌蹭到别的空白面上，浪费了），但是……他可以拿男 $1$ 亲过的那张纸的反面去亲！如下图：
最后是男 $5$。这次，男 $5$ 终于可以用男 $3$ 用过的那张纸的反面去亲女生了！
整体的纸巾使用情况如图：
正好一面不落，全都用过了！
对于 $n=6$ 的情况。我们发现，可以“浪费”掉男 $1$ 亲过的那张纸的反面，最终情况如下图：
按照这个思路，我们很快就能构造出 $n=7,8,9,...$ 的方案。
感觉正解已经出来了，那么总结一下规律吧。
规律及正确性证明
不妨设 $m=\lfloor\frac{3n}{2}\rfloor$，即纸的总张数。
则整个方案如下图所示（注意顺序）：
（第五步中，编号 $1$ 的纸巾的两个面标反了；这一步实际上可以通过省去 $1$ 号纸巾简化为两张纸，下文中提到的我的提交记录中使用的就是两张纸的亲法）
我们来证明一下这个方案的正确性。
除了男 $2$ 外，其余男生用的编号最大的纸巾的编号为
$$\bigg\lfloor\frac{n-2}{2}\bigg\rfloor+1$$
它等于
$$\bigg\lfloor\frac{n}{2}-1\bigg\rfloor+1$$
也就是
$$\bigg\lfloor\frac{n}{2}\bigg\rfloor-1+1$$
最后两项抵消，得
$$\bigg\lfloor\frac{n}{2}\bigg\rfloor$$
女生和男 $2$ 一共用过 $n$ 张纸，我们发现
$$\bigg\lfloor\frac{n}{2}\bigg\rfloor+n=\bigg\lfloor\frac{n}{2}\bigg\rfloor+\frac{2n}{2}=\bigg\lfloor\frac{3n}{2}\bigg\rfloor$$
一张不多，一张不少！
再来看看一共输出了多少个数。
满打满算，因为在我们的方案中，每对男女接吻至多需要用三张纸，所以我们大胆一点，不妨假设每对男女都用了三张纸。
一共 $n^2$ 对男女，每对所需输出的数的个数为 $2+1+2\times 3=9$，一共需要 $9\times 1000^2=9\times 10^6$ 张纸，远小于题目要求的 $5\times 10^7$，所以是完全合法的！
AC 代码
总结了规律后，我们就有了这个提交记录中的那份代码（完全可以把 $n=2$ 的特判给删掉，因为算出来的 $p=q=0$；$n=1$ 的特判不能删，删了还得加其他特判）。代码仅供参考，方案中存在可以改动的地方，所以请不要抄袭代码。
再次提醒，代码中第五步的操作只用了两张纸，与上文图中所示方法有所不同（省去了 $1$ 号纸巾）。
建议使用较快的输出，毕竟输出量还是挺大的。
尾声
感谢您的阅读，若有不妥之处还请批评指正。
