F-智乃的Chino语言随机数生成器(hard version)

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

本题有easy版本，通过hard版本可以直接通过easy版本，区别仅在easy版本有额外限制条件，位于输入描述。

如果您仅想提交一个文本文件而非代码，可在选择提交语言处选择语言为php，在不使用php语法的情况下，可以当成是直接提交答案。

如您需要spj代码，本题提供了c++/java/python三种语言的spj，仅供参考。

点击后面下载：cvm.zip

智乃现在有一个随机数生成器，它有 $p$ %的概率生成 $0$ ， $(1-p\%)$ 的概率生成 $1$ 。

智乃想通过算法将其改造成 $q$ %的概率生成 $0$ ， $(1-q\%)$ 的概率生成 $1$ 。

具体来讲，智乃将使用她自定义的Chino语言来实现这个算法。

Chino语言的内存结构非常简单，是一个长度大小为 $10^6+1$ 的比特位数组（数组只能存储 $0$ 和 $1$ ），数组的第一个可用下标为 $0$ ，最后一个可用下标为 $10^6$ 。我们使用 $R[x]$ 表示Chino语言内存结构的第 $x$ 位的值。

在一开始，Chino语言的内存结构中所有的比特位初始值都为 $0$ 。

Chino语言还有rand、if、test、return四种操作符。

rand x，表示随机生成一个随机数存储到 $R[x]$ ，有 $p$ %的概率生成 $0$ ， $(1-p\%)$ 的概率生成 $1$ 。
test x y z，表示判断 $R[y]$ 和 $R[z]$ 的值是否相同，若相同则生成一个 $1$ 存储到 $R[x]$ ，否则生成 $0$ 存储到 $R[x]$ 。
if x，表示判断 $R[x]$ 的值是否为 $1$ ，若不为 $1$ 则跳过下一条操作符。（注意连续使用多条if指令可能并不与常见语言的预期相同，这里仅跳过下一条操作符，而非整体，没有语句块的概念，当两if操作符连续时，第一条不满足时只会跳过下一个if这个判断操作，后面的逻辑是正常执行的）
return x，表示立即停止程序，并给出 $R[x]$ 的值作为程序运行的最终结果。（即使后面仍然存在其他操作也不再继续执行）

对于任何一个Chino语言代码，必须保证在任何分支可能被执行的情况下，都明确的存在返回值，否则被当成答案错误处理。

智乃现在想让你编写一个Chino语言代码，使得最终有 $q$ %的概率生成 $0$ ， $(1-q\%)$ 的概率生成 $1$ ，要求最终使用的操作符数目不多于 $3\times 10^3$ 。

你的代码将被运行在CVM（Chino virtual machine），进行 $2.5\times 10^4$ 次伪随机测试（每次判题时使用 $10^4$ 组相同的随机数种子），若最终随机数产生概率的绝对误差不多于 $2\%$ ，则答案正确。

可以用数学方法计算出得出，对于99.999%的数据分布，保证使用正确的随机数生成器，该测试与标准的误差不大于 $1\%$ ，即保证你的代码的误差不大于1%时可以确保通过题目。

由于判题时每次使用的随机数种子相同，请勿提交相同的代码，减少评测机压力。

输入描述:

仅一行两个正整数表示概率，百分数。

输出描述:

第一行输出一个正整数表示Chino语言代码操作的数目。

接下来行，每行一个Chino语言操作符以及若干操作数，具体定义见上文。

示例1

输入

复制

50 50

输出

复制

5
rand 0
test 1000000 1000000 1000000
if 0
return 1000000
return 999999

说明

一开始的内存结构为

执行完rand 0后
0/1表示有50%的概率是0,50%的概率是1。
执行完test 1000000 1000000 1000000后
接下来如果R[0]时1，就返回R[1000000]的值（也就是1）。
否则跳过返回R[1000000]，返回R[999999]的值（也就是0）。
重复进行若干次此时，期望无限接近0.5。