DDCTF2018 - 黑盒测试（先放一道老题）

源码分析

解包后得到两个文件，一个elf，另一个txt文件，名字是flag-48ee204317，源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
__int64 __fastcall main(int a1, char **a2, char **a3)
{
  __int64 v4; // rbx
  int i; // [rsp+Ch] [rbp-84h]
  FILE *stream; // [rsp+10h] [rbp-80h]
  char s[8]; // [rsp+20h] [rbp-70h] BYREF
  int v8; // [rsp+28h] [rbp-68h]
  __int16 v9; // [rsp+2Ch] [rbp-64h]
  char v10; // [rsp+2Eh] [rbp-62h]
  char filename[8]; // [rsp+30h] [rbp-60h] BYREF
  __int64 v12; // [rsp+38h] [rbp-58h]
  __int64 v13; // [rsp+40h] [rbp-50h]
  int v14; // [rsp+48h] [rbp-48h]
  __int16 v15; // [rsp+4Ch] [rbp-44h]
  __int64 ptr[3]; // [rsp+50h] [rbp-40h] BYREF
  __int64 v17; // [rsp+68h] [rbp-28h]
  __int64 v18; // [rsp+70h] [rbp-20h]
  unsigned __int64 v19; // [rsp+78h] [rbp-18h]

  v19 = __readfsqword(0x28u);
  *(_QWORD *)filename = 0LL;
  v12 = 0LL;
  v13 = 0LL;
  v14 = 0;
  v15 = 0;
  *(_QWORD *)s = 0LL;
  v8 = 0;
  v9 = 0;
  v10 = 0;
  memset(ptr, 0, sizeof(ptr));
  v17 = 0LL;
  v18 = 0LL;
  puts("Please input your password!");//首先输入的是password
  fgets(s, 15, stdin);
  BYTE2(v8) = 0;
  for ( i = 0; i <= 9 && isalnum(s[i]); ++i )
    ;
  if ( i == 10 )
  {
    sprintf(filename, "flag-%s.txt", s);
      //通过这里可以知道，输入的s(也即是password就是txt附件的名称48ee204317)
    stream = fopen(filename, "r");
    if ( stream )
    {
      fread(ptr, 0x17uLL, 1uLL, stream);
      LOBYTE(v17) = 0;
      fclose(stream);
      puts("---------------------[Welcome To ReverseMe!]---------------------");
      puts("\n\nPlease Input Your Passcode,If You See print the \"Binggo\" string,Congratulations,You Win. Good luck!");
        //接下来输入的是passcode，经过分析其实就是虚拟机中的opcode，并且让程序输出Binggo，即可获得flag
      v4 = operator new(0xAA0uLL);
      sub_401E98(v4);
      if ( !(unsigned int)sub_4016BD(v4) )
      {
        printf("Error code:%x\n", (unsigned int)dword_6038E0);
        exit(0);
      }
      fgets((char *)(v4 + 16), 100, stdin);//这里可以看出passcode是从v4+16开始存储的
      if ( memcmp("exit", (const void *)(v4 + 16), 4uLL) )
      {
        sub_401A48(v4);//经过401A48的处理
        if ( byte_603F00 )//判定success的条件莫名其妙，使用交叉引用
          printf("Success!\nYour flag is %s\n", (const char *)ptr);
        else
          puts("Failed!");
      }
      sub_401B8B(v4);
      return 0LL;
    }
    else
    {
      puts("Could not read the flag! Please check your password.");
      return 1LL;
    }
  }
  else
  {
    puts("Invalid password!");
    return 1LL;
  }
}

sub_401E98是关键函数，步入之后的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
__int64 __fastcall sub_401A48(__int64 a1)
{
  char v2; // [rsp+13h] [rbp-1Dh]
  int i; // [rsp+14h] [rbp-1Ch]
  int j; // [rsp+18h] [rbp-18h]

  if ( a1 && a1 != -16 )
  {
    for ( i = 0; i < strlen((const char *)(a1 + 16)); ++i )
    {
      v2 = *(_BYTE *)(a1 + i + 16);//读取passcode的第i位
      if ( i + 1 != strlen((const char *)(a1 + 16)) )
        *(_BYTE *)(a1 + 664) = *(_BYTE *)(a1 + i + 1 + 16);//*(a1+664)=passcode[i+1]
      for ( j = 0; j <= 8; ++j )//说明有9种opcode
      {
        if ( byte_603900[v2] == *(_BYTE *)(a1 + *(int *)(a1 + 4 * (j + 72LL) + 8) + 408) )
        {//byte_603900显然需要dump出来
          *(_QWORD *)(a1 + 672) = *(_QWORD *)(a1 + 8 * (*(int *)(a1 + 4 * (j + 72LL) + 8) + 84LL) + 8);
          (*(void (__fastcall **)(__int64))(a1 + 672))(a1);
            //这里是一个fastcall，也是一种函数调用方式，很容易忽略，应该对应了汇编的call rax
        }
      }
    }
  }
  return 0LL;
}

乍一看其实比较难懂，此时结合汇编：

注意到有个call rax,应该就是靠这个来实现跳转到各个handle内，而该函数应该就是Dispatcher，这里再回去看代码应该就很好理解了。

动调找opcode

有了上面的分析，下面开始进行动态调试，在byte_603900处下断点，在虚拟机中输入password绕过，再输入passcode：

我们注意到，要想进行到跳转语句，必须满足表达式

1
byte_603900[v2] == *(_BYTE *)(a1 + *(int *)(a1 + 4 * (j + 72LL) + 8) + 408)

而v2是我们输入的passcode，由此我们可以得出，byte_603900的作用应该是让opcode与我们输入的passcode进行一个一一对应的映射，此处我们在动态调试的情况下用idc脚本dump出符合所有 的opcode，就可以找出我们所输入的passcode是由那些字符（opcode）组成的。

我们在调用dispatch的地方下断点，F7步入后，调用idc脚本：

1
2
3
4
5
6
7
8
9
10
#include<idc.idc>
static main()
{
	auto j;
	auto a1=0x17BA8B0;//此处的a1每次动态都不一样
	for(j=0;j<=8;++j)
	{
		Message("0x%x,",Byte(a1+Byte(a1+4*(j+72)+8)+408));
    }
}

这样我们就可以得到opcode：0x2a,0x27,0x3e,0x5a,0x3f,0x4e,0x6a,0x2b,0x28

接着再从ida扒出byte_603900的数据，找出映射之前组成passcode的字符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
byte_603900 = [0x02, 0x00, 0x00, 0x0E, 0x16, 0x54, 0x20, 0x18, 0x11, 0x45,
0x50, 0x59, 0x58, 0x53, 0x00, 0x08, 0x44, 0x2D, 0x46, 0x39,
0x00, 0x54, 0x42, 0x01, 0x3C, 0x0F, 0x00, 0x07, 0x17, 0x00,
0x56, 0x21, 0x00, 0x37, 0x6D, 0x2B, 0x2A, 0x6E, 0x59, 0x5D,
0x47, 0x3A, 0x4A, 0x34, 0x44, 0x48, 0x43, 0x6C, 0x3F, 0x59,
0x25, 0x33, 0x55, 0x2F, 0x31, 0x68, 0x27, 0x34, 0x7C, 0x28,
0x67, 0x59, 0x00, 0x52, 0x00, 0x26, 0x00, 0x3E, 0x56, 0x4E,
0x33, 0x21, 0x45, 0x6D, 0x60, 0x39, 0x46, 0x72, 0x6D, 0x4D,
0x54, 0x40, 0x00, 0x74, 0x57, 0x73, 0x72, 0x7A, 0x47, 0x45,
0x00, 0x71, 0x00, 0x4A, 0x35, 0x70, 0x3B, 0x36, 0x2E, 0x26,
0x2C, 0x6C, 0x4A, 0x00, 0x7C, 0x63, 0x35, 0x57, 0x4D, 0x41,
0x43, 0x62, 0x00, 0x68, 0x37, 0x00, 0x5A, 0x6A, 0x6B, 0x7C,
0x29, 0x69, 0x4C, 0x70, 0x50, 0x71, 0x26, 0x36, 0x3C, 0x06,
0x1B, 0x00, 0x3C, 0x30, 0x00, 0x00, 0x00, 0x4C, 0x0B, 0x4B,
0x48, 0x08, 0x54, 0x47, 0x12, 0x09, 0x24, 0x00, 0x00, 0x24,
0x40, 0x0D, 0x39, 0x06, 0x5C, 0x2C, 0x1A, 0x2D, 0x0A, 0x38,
0x35, 0x37, 0x16, 0x3B, 0x00, 0x24, 0x48, 0x00, 0x49, 0x00,
0x37, 0x08, 0x1F, 0x24, 0x45, 0x1D, 0x11, 0x40, 0x2F, 0x4A,
0x08, 0x15, 0x00, 0x11, 0x00, 0x1A, 0x22, 0x41, 0x52, 0x5B,
0x0B, 0x45, 0x31, 0x19, 0x43, 0x19, 0x1E, 0x0A, 0x21, 0x05,
0x4D, 0x59, 0x38, 0x34, 0x09, 0x36, 0x2F, 0x43, 0x02, 0x53,
0x12, 0x2F, 0x4C, 0x21, 0x0D, 0x3C, 0x31, 0x2E, 0x37, 0x08,
0x30, 0x29, 0x32, 0x2F, 0x00, 0x1A, 0x14, 0x41, 0x53, 0x15,
0x21, 0x00, 0x08, 0x13, 0x38, 0x5C, 0x36, 0x3B, 0x50, 0x00,
0x2F, 0x1E, 0x57, 0x00, 0x30, 0x2E, 0x0C, 0x2E, 0x37, 0x52,
0x1C, 0x33, 0x34, 0x11, 0x38, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00]
passcode = [0x2a, 0x27, 0x3e, 0x5a, 0x3f, 0x4e, 0x6a, 0x2b, 0x28]
opcode = []
for i in passcode:
    opcode.append(chr(byte_603900.index(i)))
print(opcode)

最终得到映射前的opcode：

1
[’$’, ‘8’, ‘C’, ‘t’, ‘0’, ‘E’, ‘u’, ‘#’, ‘;’]

再次动调跟踪每个opcode对应的case

有了opcode，接下来的工作是跟踪每一个opcode对应的case。

通过对byte_603F00的交叉引用，找到其直接调用的函数

我们发现该函数是通过fastcall进行调用的，说明该函数应该就是其中的一个case，我们再对sub_401D33D进行交叉引用：

找到了每个case对应的函数。

接下来，我们通过动态调试，在输入passcode的地方输入之前得到的opcode，此处仅以opcode(‘8’)演示

在此处下断点后，if语句种的条件应当是成立的，继续F8，在fastall的地方F7步入，我们就可以找到opcode(8)对应的case

用同样的方法，我们可以找到每个opcode对应的case：

1
2
3
4
5
6
7
8
9
$ -> sub_400DC1(func1)
8 -> sub_400E7A(func2)
C -> sub_400F3A(func3)
t -> sub_401064(func4)
0 -> sub_4011C9(func5)
E -> sub_40133D(func6)
u -> sub_4012F3(func7)
# -> sub_4014B9(func8)
; -> sub_400CF1(func9)

对每个case的功能进行分析

接下来是SG大爹的硬核分析环节：

我们先把伪代码进行初步的简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func1:
	if *(a1 + 288) < *(a1 + 292)
		*(a1 + 665) = *((a1 + 8) + (int)(a1 + 288));

func2:
	if *(a1 + 288) < *(a1 + 292)
        *((int)(a1 + 288) + (a1 + 8)) = *(a1 + 665)

func3:
	if *(a1 + 288) < *(a1 + 292)
		*(a1 + 665) = *(a1 + 665) + *(a1 + 664) - 33

func4
	if *(a1 + 288) < *(a1 + 292)
		*(_BYTE *)(a1 + 665) = *(_BYTE *)(a1 + 665) - *(_BYTE *)(a1 + 664) + 33
		if (a1 + 665)
			++(a1 + 665)

func5:
	if *(a1 + 288) < *(a1 + 292)
		++*(a1 + 288)

func6:
	check()

func7:
	if *(a1 + 288) > 0
		--*(a1 + 288)

func8:
	++(a1 + 288)
	if *(a1 + 288) < *(a1 + 292) and *(a1 + 664) - 48 <= 41
		*((a1 + 280) + (int)(a1 + 288) + a1) = *((a1 + 16) + *(a1 + 288) + *(a1 + 664) - 48) - 49

func9:
	for (i = 0; i < *(a1 + 664); ++i)
    	++*(a1 + 288);
    if *(a1 + 664) - 16 <= 89
    	*((a1 + 280) + (int)(a1 + 288) + a1) = *((a1 + 16) + *(a1 + 288) + *(a1 + 664) - 48) - 49
    	
check()
	if (a1 + 664) == 's'
		s = ((a1 + 8) + (a1 + 288)), len = 20
		if (right(s))
			success!

其中，check()的逻辑是

1
2
3
4
if (a1 + 664) == 's'
		s = ((a1 + 8) + (a1 + 288)), len = 20
		if (right(s))
			success!

然后进行动态调试，可以发现

  • +655: 临时变量tmp
  • +8: str = “PaF0!&Prv}H{ojDQ#7v=”
  • +288: pt
  • +16: 我们输入的passcode(input)
  • +664: 下一位输入(next, 即input[i + 1])

并且，一些奇怪的东西如下：

  • *((a1 + 280) + (int)(a1 + 288) + a1): str[pt]
  • ((a1 + 16) + (a1 + 288) + *(a1 + 664) - 48): input[pt + input[i] - 48]

那么，可以拿出伪代码的进一步分析了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func1($):
	temp = str[pt]
func2(8):
	str[pt] = temp
func3(C):
	temp = temp + next - 33
func4(t):
	temp = temp - next + 33
func5(0):
	++pt
func6(E):
	check()
func7(u):
	--pt
func8(#):
	str[pt] = input[pt + next - 48] - 49
func9(;):
	for (i = 0; i < next; ++i) ++pt;
	str[pt] = input[pt + next - 48] - 49

并且，在check()中，我们还发现：程序的目的是将str = “PaF0!&Prv}H{ojDQ#7v=” 转换成 str = “Binggo”，然后我们才可以得到flag

显然地，str的位数远大于”Binggo”，我们得考虑在PaF0!&P的第二个P处用’\0’将字符串截断

构造passcode使程序输出Binggo

从头开始构造吧

首先看P -> B，我们先取出’P’，用’$’使得temp = str[pt]，此时pt = 0，则temp = ‘P’

两者的ASCII分别是80, 66，考虑用’t操作’

$80 - next + 33 = 66$，显然$next = 47$，即’/‘

然后分别用’8’’0’来进行更新，并且将pt指针后移一位

综上，第一步的opcode应该是$t/80

同理，PaF0!&转换成Binggo需要的opcode应该是$t/80$C)80$CI80$CX80$Cg80$Cj80

现在该考虑截断操作了

这里我们不能用func3来构造了，这样得到的是一个不可见字符

那只能考虑func8来进行一下复杂操作了

我们考虑在P -> B的时候额外插入一个111来让pt指向第七个字符时直接构造’\0’，最后调整pt到str前端，最后用’E’调用check()并用’s’满足check()的条件

最终的passcode就是

$t/81110$C)80$CI80$CX80$Cg80$Cj80#0uuuuuuuuEs

提交passcode得到flag

TSCTF-J2022 - 🤖

0x01 分析main函数逻辑

首先分析主函数逻辑

1666878585692

结合hint 发现主函数其实就干了下面这件事，那么显然v4就是整个虚拟机的 opcode，所有的操作都是通过对v4进行调度来实现，知道了这一点，先动调把程序未开始执行的v4初始化状态给dump下来，并且根据hint，所有的数据都是 int16 型的，写个脚本转化一下即可

1
2
3
4
5
6
7
8
9
10
while true do
	i = mem[IP]
 	a = mem[i + 0]
 	b = mem[i + 1]
 	r = mem[i + 2]
 	mem[ip] = i + 3
 	f = nor(mem[a], mem[b])
 	mem[r] = f
 	mem[SHIFT_REG] = ((f >> 15) & 1) | ((f & 0x7FFF) << 1)
end

再写脚本实现一下main函数，先测试一下能否正常运行，并判断出 flag 长度为35位，发现程序可以正常输出wrong，说明main函数逻辑是正确的，那么接下来就是要搞明白这个 v4 到底是怎么只通过一些列 NOR 指令判断你输进去的 flag 到底对不对的，于是一个基本思路就有了。

0x02 生成指令

1666879491002

1666879635509

然后空白✌的答复是

1666878927068

可以硬刚，那就试试呗，写程序实现之前提到的思路，先写脚本把main函数的每一轮循环都变成 NOR 指令的格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
unsigned short opcode[] =
{
  	300, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8543, 8543, 7, 7, 7, 3, 312, 312, 7, 7, 7, 0, 314, 1, 313, 313, 7, 7, 7, 4, 8540, 8540, 7, 7, 7, 3, 332, 332, 7, 7, 7, 0, 334, 1, 333, 333, 7, 7, 7, 4, 8541, 8541, 7, 7, 7, 3, 352, 352, 7, 7, 7, 0, 354, 1, 353, 353, 7, 7, 7, 4, 8542, 8542, 7, 7, 7, 3, 372, 372, 7, 7, 7, 0, 374, 1, 373, 373, 7, 7, 7, 4, 8544, 8544, 7, 7, 7, 3, 392, 392, 7, 7, 7, 0, 394, 1, 393, 393, 7, 7, 7, 4, 8541, 8541, 7, 7, 7, 3, 412, 412, 7, 7, 7, 0, 414, 1, 413, 413, 7, 7, 7, 4, 8550, 8550, 7, 7, 7, 3, 432, 432, 7, 7, 7, 0, 434, 1, 433, 433, 7, 7, 7, 4, 8555, 8555, 7, 7, 7, 3, 452, 452, 7, 7, 7, 0, 454, 1, 453, 453, 7, 7, 7, 4, 8553, 8553, 7, 7, 7, 3, 472, 472, 7, 7, 7, 0, 474, 1, 473, 473, 7, 7, 7, 4, 8556, 8556, 7, 7, 7, 3, 492, 492, 7, 7, 7, 0, 494, 1, 493, 493, 7, 7, 7, 4, 8557, 8557, 7, 7, 7, 3, 512, 512, 7, 7, 7, 0, 514, 1, 513, 513, 7, 7, 7, 4, 8547, 8547, 7, 7, 7, 3, 532, 532, 7, 7, 7, 0, 534, 1, 533, 533, 7, 7, 7, 4, 8550, 8550, 7, 7, 7, 3, 552, 552, 7, 7, 7, 0, 554, 1, 553, 553, 7, 7, 7, 4, 8558, 8558, 7, 7, 7, 3, 572, 572, 7, 7, 7, 0, 574, 1, 573, 573, 7, 7, 7, 4, 8539, 8539, 7, 7, 7, 3, 592, 592, 7, 7, 7, 0, 594, 1, 593, 593, 7, 7, 7, 4, 8557, 8557, 7, 7, 7, 3, 612, 612, 7, 7, 7, 0, 614, 1, 613, 613, 7, 7, 7, 4, 8538, 8538, 7, 7, 7, 3, 632, 632, 7, 7, 7, 0, 634, 1, 633, 633, 7, 7, 7, 4, 8550, 8550, 7, 7, 7, 3, 652, 652, 7, 7, 7, 0, 654, 1, 653, 653, 7, 7, 7, 4, 8552, 8552, 7, 7, 7, 3, 672, 672, 7, 7, 7, 0, 674, 1, 673, 673, 7, 7, 7, 4, 8540, 8540, 7, 7, 7, 3, 692, 692, 7, 7, 7, 0, 694, 1, 693, 693, 7, 7, 7, 4, 8542, 8542, 7, 7, 7, 3, 712, 712, 7, 7, 7, 0, 714, 1, 713, 713, 7, 7, 7, 4, 8548, 8548, 7, 7, 7, 3, 732, 732, 7, 7, 7, 0, 734, 1, 733, 733, 7, 7, 7, 4, 8549, 8549, 7, 7, 7, 3, 752, 752, 7, 7, 7, 0, 754, 1, 753, 753, 7, 7, 7, 4, 766, 766, 7, 7, 7, 0, 768, 775, 767, 767, 7, 7, 7, 0, 0, 781, 781, 7, 7, 7, 0, 783, 1, 782, 782, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8503, 801, 801, 7, 7, 7, 0, 803, 1, 802, 802, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8504, 821, 821, 7, 7, 7, 0, 823, 1, 822, 822, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8505, 841, 841, 7, 7, 7, 0, 843, 1, 842, 842, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8506, 861, 861, 7, 7, 7, 0, 863, 1, 862, 862, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8507, 881, 881, 7, 7, 7, 0, 883, 1, 882, 882, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8508, 901, 901, 7, 7, 7, 0, 903, 1, 902, 902, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8509, 921, 921, 7, 7, 7, 0, 923, 1, 922, 922, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8510, 941, 941, 7, 7, 7, 0, 943, 1, 942, 942, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8511, 961, 961, 7, 7, 7, 0, 963, 1, 962, 962, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8512, 981, 981, 7, 7, 7, 0, 983, 1, 982, 982, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8513, 1001, 1001, 7, 7, 7, 0, 1003, 1, 1002, 1002, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8514, 1021, 1021, 7, 7, 7, 0, 1023, 1, 1022, 1022, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8515, 1041, 1041, 7, 7, 7, 0, 1043, 1, 1042, 1042, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8516, 1061, 1061, 7, 7, 7, 0, 1063, 1, 1062, 1062, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8517, 1081, 1081, 7, 7, 7, 0, 1083, 1, 1082, 1082, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8518, 1101, 1101, 7, 7, 7, 0, 1103, 1, 1102, 1102, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8519, 1121, 1121, 7, 7, 7, 0, 1123, 1, 1122, 1122, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8520, 1141, 1141, 7, 7, 7, 0, 1143, 1, 1142, 1142, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8521, 1161, 1161, 7, 7, 7, 0, 1163, 1, 1162, 1162, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8522, 1181, 1181, 7, 7, 7, 0, 1183, 1, 1182, 1182, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8523, 1201, 1201, 7, 7, 7, 0, 1203, 1, 1202, 1202, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8524, 1221, 1221, 7, 7, 7, 0, 1223, 1, 1222, 1222, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8525, 1241, 1241, 7, 7, 7, 0, 1243, 1, 1242, 1242, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8526, 1261, 1261, 7, 7, 7, 0, 1263, 1, 1262, 1262, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8527, 1281, 1281, 7, 7, 7, 0, 1283, 1, 1282, 1282, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8528, 1301, 1301, 7, 7, 7, 0, 1303, 1, 1302, 1302, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8529, 1321, 1321, 7, 7, 7, 0, 1323, 1, 1322, 1322, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8530, 1341, 1341, 7, 7, 7, 0, 1343, 1, 1342, 1342, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8531, 1361, 1361, 7, 7, 7, 0, 1363, 1, 1362, 1362, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8532, 1381, 1381, 7, 7, 7, 0, 1383, 1, 1382, 1382, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8533, 1401, 1401, 7, 7, 7, 0, 1403, 1, 1402, 1402, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8534, 1421, 1421, 7, 7, 7, 0, 1423, 1, 1422, 1422, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8535, 1441, 1441, 7, 7, 7, 0, 1443, 1, 1442, 1442, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8536, 1461, 1461, 7, 7, 7, 0, 1463, 1, 1462, 1462, 7, 7, 7, 6, 5, 5, 7, 7, 7, 8537, 8503, 8503, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 1667, 1667, 7, 7, 7, 0, 1670, 0, 0, 8239, 8239, 1668, 8492, 8492, 1669, 1682, 1682, 7, 7, 7, 0, 1685, 0, 0, 8239, 8239, 1683, 1669, 1669, 1684, 1683, 1684, 7, 7, 7, 7, 7, 7, 1669, 1706, 1706, 7, 7, 7, 0, 1709, 0, 0, 8492, 8492, 1707, 1668, 1668, 1708, 1707, 1708, 7, 7, 7, 7, 7, 7, 1668, 1668, 1669, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8504, 8504, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 1928, 1928, 7, 7, 7, 0, 1931, 0, 0, 8239, 8239, 1929, 8491, 8491, 1930, 1943, 1943, 7, 7, 7, 0, 1946, 0, 0, 8239, 8239, 1944, 1930, 1930, 1945, 1944, 1945, 7, 7, 7, 7, 7, 7, 1930, 1967, 1967, 7, 7, 7, 0, 1970, 0, 0, 8491, 8491, 1968, 1929, 1929, 1969, 1968, 1969, 7, 7, 7, 7, 7, 7, 1929, 1929, 1930, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8505, 8505, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 2189, 2189, 7, 7, 7, 0, 2192, 0, 0, 8239, 8239, 2190, 8483, 8483, 2191, 2204, 2204, 7, 7, 7, 0, 2207, 0, 0, 8239, 8239, 2205, 2191, 2191, 2206, 2205, 2206, 7, 7, 7, 7, 7, 7, 2191, 2228, 2228, 7, 7, 7, 0, 2231, 0, 0, 8483, 8483, 2229, 2190, 2190, 2230, 2229, 2230, 7, 7, 7, 7, 7, 7, 2190, 2190, 2191, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8506, 8506, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 2450, 2450, 7, 7, 7, 0, 2453, 0, 0, 8239, 8239, 2451, 8492, 8492, 2452, 2465, 2465, 7, 7, 7, 0, 2468, 0, 0, 8239, 8239, 2466, 2452, 2452, 2467, 2466, 2467, 7, 7, 7, 7, 7, 7, 2452, 2489, 2489, 7, 7, 7, 0, 2492, 0, 0, 8492, 8492, 2490, 2451, 2451, 2491, 2490, 2491, 7, 7, 7, 7, 7, 7, 2451, 2451, 2452, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8507, 8507, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 2711, 2711, 7, 7, 7, 0, 2714, 0, 0, 8239, 8239, 2712, 8485, 8485, 2713, 2726, 2726, 7, 7, 7, 0, 2729, 0, 0, 8239, 8239, 2727, 2713, 2713, 2728, 2727, 2728, 7, 7, 7, 7, 7, 7, 2713, 2750, 2750, 7, 7, 7, 0, 2753, 0, 0, 8485, 8485, 2751, 2712, 2712, 2752, 2751, 2752, 7, 7, 7, 7, 7, 7, 2712, 2712, 2713, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8508, 8508, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 2972, 2972, 7, 7, 7, 0, 2975, 0, 0, 8239, 8239, 2973, 8475, 8475, 2974, 2987, 2987, 7, 7, 7, 0, 2990, 0, 0, 8239, 8239, 2988, 2974, 2974, 2989, 2988, 2989, 7, 7, 7, 7, 7, 7, 2974, 3011, 3011, 7, 7, 7, 0, 3014, 0, 0, 8475, 8475, 3012, 2973, 2973, 3013, 3012, 3013, 7, 7, 7, 7, 7, 7, 2973, 2973, 2974, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8509, 8509, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 3233, 3233, 7, 7, 7, 0, 3236, 0, 0, 8239, 8239, 3234, 8487, 8487, 3235, 3248, 3248, 7, 7, 7, 0, 3251, 0, 0, 8239, 8239, 3249, 3235, 3235, 3250, 3249, 3250, 7, 7, 7, 7, 7, 7, 3235, 3272, 3272, 7, 7, 7, 0, 3275, 0, 0, 8487, 8487, 3273, 3234, 3234, 3274, 3273, 3274, 7, 7, 7, 7, 7, 7, 3234, 3234, 3235, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8510, 8510, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 3494, 3494, 7, 7, 7, 0, 3497, 0, 0, 8239, 8239, 3495, 8501, 8501, 3496, 3509, 3509, 7, 7, 7, 0, 3512, 0, 0, 8239, 8239, 3510, 3496, 3496, 3511, 3510, 3511, 7, 7, 7, 7, 7, 7, 3496, 3533, 3533, 7, 7, 7, 0, 3536, 0, 0, 8501, 8501, 3534, 3495, 3495, 3535, 3534, 3535, 7, 7, 7, 7, 7, 7, 3495, 3495, 3496, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8511, 8511, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 3755, 3755, 7, 7, 7, 0, 3758, 0, 0, 8239, 8239, 3756, 8491, 8491, 3757, 3770, 3770, 7, 7, 7, 0, 3773, 0, 0, 8239, 8239, 3771, 3757, 3757, 3772, 3771, 3772, 7, 7, 7, 7, 7, 7, 3757, 3794, 3794, 7, 7, 7, 0, 3797, 0, 0, 8491, 8491, 3795, 3756, 3756, 3796, 3795, 3796, 7, 7, 7, 7, 7, 7, 3756, 3756, 3757, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 3830, 3830, 7, 7, 7, 0, 3833, 0, 0, 8512, 8512, 3831, 8472, 8472, 3832, 3845, 3845, 7, 7, 7, 0, 3848, 0, 0, 8512, 8512, 3846, 3832, 3832, 3847, 3846, 3847, 7, 7, 7, 7, 7, 7, 3832, 3869, 3869, 7, 7, 7, 0, 3872, 0, 0, 8472, 8472, 3870, 3831, 3831, 3871, 3870, 3871, 7, 7, 7, 7, 7, 7, 3831, 3831, 3832, 7, 7, 7, 8239, 3899, 3899, 7, 7, 7, 0, 3902, 0, 0, 8239, 8239, 3900, 8499, 8499, 3901, 3914, 3914, 7, 7, 7, 0, 3917, 0, 0, 8239, 8239, 3915, 3901, 3901, 3916, 3915, 3916, 7, 7, 7, 7, 7, 7, 3901, 3938, 3938, 7, 7, 7, 0, 3941, 0, 0, 8499, 8499, 3939, 3900, 3900, 3940, 3939, 3940, 7, 7, 7, 7, 7, 7, 3900, 3900, 3901, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 3974, 3974, 7, 7, 7, 0, 3977, 0, 0, 8513, 8513, 3975, 8470, 8470, 3976, 3989, 3989, 7, 7, 7, 0, 3992, 0, 0, 8513, 8513, 3990, 3976, 3976, 3991, 3990, 3991, 7, 7, 7, 7, 7, 7, 3976, 4013, 4013, 7, 7, 7, 0, 4016, 0, 0, 8470, 8470, 4014, 3975, 3975, 4015, 4014, 4015, 7, 7, 7, 7, 7, 7, 3975, 3975, 3976, 7, 7, 7, 8239, 4043, 4043, 7, 7, 7, 0, 4046, 0, 0, 8239, 8239, 4044, 8479, 8479, 4045, 4058, 4058, 7, 7, 7, 0, 4061, 0, 0, 8239, 8239, 4059, 4045, 4045, 4060, 4059, 4060, 7, 7, 7, 7, 7, 7, 4045, 4082, 4082, 7, 7, 7, 0, 4085, 0, 0, 8479, 8479, 4083, 4044, 4044, 4084, 4083, 4084, 7, 7, 7, 7, 7, 7, 4044, 4044, 4045, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8514, 8514, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 4304, 4304, 7, 7, 7, 0, 4307, 0, 0, 8239, 8239, 4305, 8498, 8498, 4306, 4319, 4319, 7, 7, 7, 0, 4322, 0, 0, 8239, 8239, 4320, 4306, 4306, 4321, 4320, 4321, 7, 7, 7, 7, 7, 7, 4306, 4343, 4343, 7, 7, 7, 0, 4346, 0, 0, 8498, 8498, 4344, 4305, 4305, 4345, 4344, 4345, 7, 7, 7, 7, 7, 7, 4305, 4305, 4306, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8515, 8515, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 4565, 4565, 7, 7, 7, 0, 4568, 0, 0, 8239, 8239, 4566, 8477, 8477, 4567, 4580, 4580, 7, 7, 7, 0, 4583, 0, 0, 8239, 8239, 4581, 4567, 4567, 4582, 4581, 4582, 7, 7, 7, 7, 7, 7, 4567, 4604, 4604, 7, 7, 7, 0, 4607, 0, 0, 8477, 8477, 4605, 4566, 4566, 4606, 4605, 4606, 7, 7, 7, 7, 7, 7, 4566, 4566, 4567, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8516, 8516, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 4826, 4826, 7, 7, 7, 0, 4829, 0, 0, 8239, 8239, 4827, 8484, 8484, 4828, 4841, 4841, 7, 7, 7, 0, 4844, 0, 0, 8239, 8239, 4842, 4828, 4828, 4843, 4842, 4843, 7, 7, 7, 7, 7, 7, 4828, 4865, 4865, 7, 7, 7, 0, 4868, 0, 0, 8484, 8484, 4866, 4827, 4827, 4867, 4866, 4867, 7, 7, 7, 7, 7, 7, 4827, 4827, 4828, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8517, 8517, 7, 7, 7, 8517, 1, 1, 7, 7, 7, 8239, 4913, 4913, 7, 7, 7, 0, 4916, 0, 0, 8239, 8239, 4914, 8502, 8502, 4915, 4928, 4928, 7, 7, 7, 0, 4931, 0, 0, 8239, 8239, 4929, 4915, 4915, 4930, 4929, 4930, 7, 7, 7, 7, 7, 7, 4915, 4952, 4952, 7, 7, 7, 0, 4955, 0, 0, 8502, 8502, 4953, 4914, 4914, 4954, 4953, 4954, 7, 7, 7, 7, 7, 7, 4914, 4914, 4915, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8518, 8518, 7, 7, 7, 8518, 1, 1, 7, 7, 7, 8239, 5000, 5000, 7, 7, 7, 0, 5003, 0, 0, 8239, 8239, 5001, 8486, 8486, 5002, 5015, 5015, 7, 7, 7, 0, 5018, 0, 0, 8239, 8239, 5016, 5002, 5002, 5017, 5016, 5017, 7, 7, 7, 7, 7, 7, 5002, 5039, 5039, 7, 7, 7, 0, 5042, 0, 0, 8486, 8486, 5040, 5001, 5001, 5041, 5040, 5041, 7, 7, 7, 7, 7, 7, 5001, 5001, 5002, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8519, 8519, 7, 7, 7, 8519, 1, 1, 7, 7, 7, 8239, 5087, 5087, 7, 7, 7, 0, 5090, 0, 0, 8239, 8239, 5088, 8482, 8482, 5089, 5102, 5102, 7, 7, 7, 0, 5105, 0, 0, 8239, 8239, 5103, 5089, 5089, 5104, 5103, 5104, 7, 7, 7, 7, 7, 7, 5089, 5126, 5126, 7, 7, 7, 0, 5129, 0, 0, 8482, 8482, 5127, 5088, 5088, 5128, 5127, 5128, 7, 7, 7, 7, 7, 7, 5088, 5088, 5089, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8520, 8520, 7, 7, 7, 8520, 1, 1, 7, 7, 7, 8239, 5174, 5174, 7, 7, 7, 0, 5177, 0, 0, 8239, 8239, 5175, 8468, 8468, 5176, 5189, 5189, 7, 7, 7, 0, 5192, 0, 0, 8239, 8239, 5190, 5176, 5176, 5191, 5190, 5191, 7, 7, 7, 7, 7, 7, 5176, 5213, 5213, 7, 7, 7, 0, 5216, 0, 0, 8468, 8468, 5214, 5175, 5175, 5215, 5214, 5215, 7, 7, 7, 7, 7, 7, 5175, 5175, 5176, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 5249, 5249, 7, 7, 7, 0, 5252, 0, 0, 8521, 8521, 5250, 8493, 8493, 5251, 5264, 5264, 7, 7, 7, 0, 5267, 0, 0, 8521, 8521, 5265, 5251, 5251, 5266, 5265, 5266, 7, 7, 7, 7, 7, 7, 5251, 5288, 5288, 7, 7, 7, 0, 5291, 0, 0, 8493, 8493, 5289, 5250, 5250, 5290, 5289, 5290, 7, 7, 7, 7, 7, 7, 5250, 5250, 5251, 7, 7, 7, 8239, 5318, 5318, 7, 7, 7, 0, 5321, 0, 0, 8239, 8239, 5319, 8469, 8469, 5320, 5333, 5333, 7, 7, 7, 0, 5336, 0, 0, 8239, 8239, 5334, 5320, 5320, 5335, 5334, 5335, 7, 7, 7, 7, 7, 7, 5320, 5357, 5357, 7, 7, 7, 0, 5360, 0, 0, 8469, 8469, 5358, 5319, 5319, 5359, 5358, 5359, 7, 7, 7, 7, 7, 7, 5319, 5319, 5320, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8522, 8522, 7, 7, 7, 8522, 1, 1, 7, 7, 7, 8239, 5405, 5405, 7, 7, 7, 0, 5408, 0, 0, 8239, 8239, 5406, 8490, 8490, 5407, 5420, 5420, 7, 7, 7, 0, 5423, 0, 0, 8239, 8239, 5421, 5407, 5407, 5422, 5421, 5422, 7, 7, 7, 7, 7, 7, 5407, 5444, 5444, 7, 7, 7, 0, 5447, 0, 0, 8490, 8490, 5445, 5406, 5406, 5446, 5445, 5446, 7, 7, 7, 7, 7, 7, 5406, 5406, 5407, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8523, 8523, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 5666, 5666, 7, 7, 7, 0, 5669, 0, 0, 8239, 8239, 5667, 8494, 8494, 5668, 5681, 5681, 7, 7, 7, 0, 5684, 0, 0, 8239, 8239, 5682, 5668, 5668, 5683, 5682, 5683, 7, 7, 7, 7, 7, 7, 5668, 5705, 5705, 7, 7, 7, 0, 5708, 0, 0, 8494, 8494, 5706, 5667, 5667, 5707, 5706, 5707, 7, 7, 7, 7, 7, 7, 5667, 5667, 5668, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 5741, 5741, 7, 7, 7, 0, 5744, 0, 0, 8524, 8524, 5742, 8472, 8472, 5743, 5756, 5756, 7, 7, 7, 0, 5759, 0, 0, 8524, 8524, 5757, 5743, 5743, 5758, 5757, 5758, 7, 7, 7, 7, 7, 7, 5743, 5780, 5780, 7, 7, 7, 0, 5783, 0, 0, 8472, 8472, 5781, 5742, 5742, 5782, 5781, 5782, 7, 7, 7, 7, 7, 7, 5742, 5742, 5743, 7, 7, 7, 8239, 5810, 5810, 7, 7, 7, 0, 5813, 0, 0, 8239, 8239, 5811, 8497, 8497, 5812, 5825, 5825, 7, 7, 7, 0, 5828, 0, 0, 8239, 8239, 5826, 5812, 5812, 5827, 5826, 5827, 7, 7, 7, 7, 7, 7, 5812, 5849, 5849, 7, 7, 7, 0, 5852, 0, 0, 8497, 8497, 5850, 5811, 5811, 5851, 5850, 5851, 7, 7, 7, 7, 7, 7, 5811, 5811, 5812, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8525, 8525, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 6071, 6071, 7, 7, 7, 0, 6074, 0, 0, 8239, 8239, 6072, 8489, 8489, 6073, 6086, 6086, 7, 7, 7, 0, 6089, 0, 0, 8239, 8239, 6087, 6073, 6073, 6088, 6087, 6088, 7, 7, 7, 7, 7, 7, 6073, 6110, 6110, 7, 7, 7, 0, 6113, 0, 0, 8489, 8489, 6111, 6072, 6072, 6112, 6111, 6112, 7, 7, 7, 7, 7, 7, 6072, 6072, 6073, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 6146, 6146, 7, 7, 7, 0, 6149, 0, 0, 8526, 8526, 6147, 8478, 8478, 6148, 6161, 6161, 7, 7, 7, 0, 6164, 0, 0, 8526, 8526, 6162, 6148, 6148, 6163, 6162, 6163, 7, 7, 7, 7, 7, 7, 6148, 6185, 6185, 7, 7, 7, 0, 6188, 0, 0, 8478, 8478, 6186, 6147, 6147, 6187, 6186, 6187, 7, 7, 7, 7, 7, 7, 6147, 6147, 6148, 7, 7, 7, 8239, 6215, 6215, 7, 7, 7, 0, 6218, 0, 0, 8239, 8239, 6216, 8492, 8492, 6217, 6230, 6230, 7, 7, 7, 0, 6233, 0, 0, 8239, 8239, 6231, 6217, 6217, 6232, 6231, 6232, 7, 7, 7, 7, 7, 7, 6217, 6254, 6254, 7, 7, 7, 0, 6257, 0, 0, 8492, 8492, 6255, 6216, 6216, 6256, 6255, 6256, 7, 7, 7, 7, 7, 7, 6216, 6216, 6217, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8527, 8527, 7, 7, 7, 8527, 1, 1, 7, 7, 7, 8239, 6302, 6302, 7, 7, 7, 0, 6305, 0, 0, 8239, 8239, 6303, 8496, 8496, 6304, 6317, 6317, 7, 7, 7, 0, 6320, 0, 0, 8239, 8239, 6318, 6304, 6304, 6319, 6318, 6319, 7, 7, 7, 7, 7, 7, 6304, 6341, 6341, 7, 7, 7, 0, 6344, 0, 0, 8496, 8496, 6342, 6303, 6303, 6343, 6342, 6343, 7, 7, 7, 7, 7, 7, 6303, 6303, 6304, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8528, 8528, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 6563, 6563, 7, 7, 7, 0, 6566, 0, 0, 8239, 8239, 6564, 8494, 8494, 6565, 6578, 6578, 7, 7, 7, 0, 6581, 0, 0, 8239, 8239, 6579, 6565, 6565, 6580, 6579, 6580, 7, 7, 7, 7, 7, 7, 6565, 6602, 6602, 7, 7, 7, 0, 6605, 0, 0, 8494, 8494, 6603, 6564, 6564, 6604, 6603, 6604, 7, 7, 7, 7, 7, 7, 6564, 6564, 6565, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8529, 8529, 7, 7, 7, 8529, 1, 1, 7, 7, 7, 8239, 6650, 6650, 7, 7, 7, 0, 6653, 0, 0, 8239, 8239, 6651, 8476, 8476, 6652, 6665, 6665, 7, 7, 7, 0, 6668, 0, 0, 8239, 8239, 6666, 6652, 6652, 6667, 6666, 6667, 7, 7, 7, 7, 7, 7, 6652, 6689, 6689, 7, 7, 7, 0, 6692, 0, 0, 8476, 8476, 6690, 6651, 6651, 6691, 6690, 6691, 7, 7, 7, 7, 7, 7, 6651, 6651, 6652, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 6725, 6725, 7, 7, 7, 0, 6728, 0, 0, 8530, 8530, 6726, 8473, 8473, 6727, 6740, 6740, 7, 7, 7, 0, 6743, 0, 0, 8530, 8530, 6741, 6727, 6727, 6742, 6741, 6742, 7, 7, 7, 7, 7, 7, 6727, 6764, 6764, 7, 7, 7, 0, 6767, 0, 0, 8473, 8473, 6765, 6726, 6726, 6766, 6765, 6766, 7, 7, 7, 7, 7, 7, 6726, 6726, 6727, 7, 7, 7, 8239, 6794, 6794, 7, 7, 7, 0, 6797, 0, 0, 8239, 8239, 6795, 8488, 8488, 6796, 6809, 6809, 7, 7, 7, 0, 6812, 0, 0, 8239, 8239, 6810, 6796, 6796, 6811, 6810, 6811, 7, 7, 7, 7, 7, 7, 6796, 6833, 6833, 7, 7, 7, 0, 6836, 0, 0, 8488, 8488, 6834, 6795, 6795, 6835, 6834, 6835, 7, 7, 7, 7, 7, 7, 6795, 6795, 6796, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 6869, 6869, 7, 7, 7, 0, 6872, 0, 0, 8531, 8531, 6870, 8495, 8495, 6871, 6884, 6884, 7, 7, 7, 0, 6887, 0, 0, 8531, 8531, 6885, 6871, 6871, 6886, 6885, 6886, 7, 7, 7, 7, 7, 7, 6871, 6908, 6908, 7, 7, 7, 0, 6911, 0, 0, 8495, 8495, 6909, 6870, 6870, 6910, 6909, 6910, 7, 7, 7, 7, 7, 7, 6870, 6870, 6871, 7, 7, 7, 8239, 6938, 6938, 7, 7, 7, 0, 6941, 0, 0, 8239, 8239, 6939, 8482, 8482, 6940, 6953, 6953, 7, 7, 7, 0, 6956, 0, 0, 8239, 8239, 6954, 6940, 6940, 6955, 6954, 6955, 7, 7, 7, 7, 7, 7, 6940, 6977, 6977, 7, 7, 7, 0, 6980, 0, 0, 8482, 8482, 6978, 6939, 6939, 6979, 6978, 6979, 7, 7, 7, 7, 7, 7, 6939, 6939, 6940, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 7013, 7013, 7, 7, 7, 0, 7016, 0, 0, 8532, 8532, 7014, 8474, 8474, 7015, 7028, 7028, 7, 7, 7, 0, 7031, 0, 0, 8532, 8532, 7029, 7015, 7015, 7030, 7029, 7030, 7, 7, 7, 7, 7, 7, 7015, 7052, 7052, 7, 7, 7, 0, 7055, 0, 0, 8474, 8474, 7053, 7014, 7014, 7054, 7053, 7054, 7, 7, 7, 7, 7, 7, 7014, 7014, 7015, 7, 7, 7, 8239, 7082, 7082, 7, 7, 7, 0, 7085, 0, 0, 8239, 8239, 7083, 8480, 8480, 7084, 7097, 7097, 7, 7, 7, 0, 7100, 0, 0, 8239, 8239, 7098, 7084, 7084, 7099, 7098, 7099, 7, 7, 7, 7, 7, 7, 7084, 7121, 7121, 7, 7, 7, 0, 7124, 0, 0, 8480, 8480, 7122, 7083, 7083, 7123, 7122, 7123, 7, 7, 7, 7, 7, 7, 7083, 7083, 7084, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8533, 8533, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 8239, 8239, 7, 7, 7, 8239, 1, 1, 7, 7, 7, 8239, 7343, 7343, 7, 7, 7, 0, 7346, 0, 0, 8239, 8239, 7344, 8494, 8494, 7345, 7358, 7358, 7, 7, 7, 0, 7361, 0, 0, 8239, 8239, 7359, 7345, 7345, 7360, 7359, 7360, 7, 7, 7, 7, 7, 7, 7345, 7382, 7382, 7, 7, 7, 0, 7385, 0, 0, 8494, 8494, 7383, 7344, 7344, 7384, 7383, 7384, 7, 7, 7, 7, 7, 7, 7344, 7344, 7345, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 7418, 7418, 7, 7, 7, 0, 7421, 0, 0, 8534, 8534, 7419, 8487, 8487, 7420, 7433, 7433, 7, 7, 7, 0, 7436, 0, 0, 8534, 8534, 7434, 7420, 7420, 7435, 7434, 7435, 7, 7, 7, 7, 7, 7, 7420, 7457, 7457, 7, 7, 7, 0, 7460, 0, 0, 8487, 8487, 7458, 7419, 7419, 7459, 7458, 7459, 7, 7, 7, 7, 7, 7, 7419, 7419, 7420, 7, 7, 7, 8239, 7487, 7487, 7, 7, 7, 0, 7490, 0, 0, 8239, 8239, 7488, 8471, 8471, 7489, 7502, 7502, 7, 7, 7, 0, 7505, 0, 0, 8239, 8239, 7503, 7489, 7489, 7504, 7503, 7504, 7, 7, 7, 7, 7, 7, 7489, 7526, 7526, 7, 7, 7, 0, 7529, 0, 0, 8471, 8471, 7527, 7488, 7488, 7528, 7527, 7528, 7, 7, 7, 7, 7, 7, 7488, 7488, 7489, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8535, 8535, 7, 7, 7, 8535, 1, 1, 7, 7, 7, 8239, 7574, 7574, 7, 7, 7, 0, 7577, 0, 0, 8239, 8239, 7575, 8482, 8482, 7576, 7589, 7589, 7, 7, 7, 0, 7592, 0, 0, 8239, 8239, 7590, 7576, 7576, 7591, 7590, 7591, 7, 7, 7, 7, 7, 7, 7576, 7613, 7613, 7, 7, 7, 0, 7616, 0, 0, 8482, 8482, 7614, 7575, 7575, 7615, 7614, 7615, 7, 7, 7, 7, 7, 7, 7575, 7575, 7576, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 7649, 7649, 7, 7, 7, 0, 7652, 0, 0, 8536, 8536, 7650, 8474, 8474, 7651, 7664, 7664, 7, 7, 7, 0, 7667, 0, 0, 8536, 8536, 7665, 7651, 7651, 7666, 7665, 7666, 7, 7, 7, 7, 7, 7, 7651, 7688, 7688, 7, 7, 7, 0, 7691, 0, 0, 8474, 8474, 7689, 7650, 7650, 7690, 7689, 7690, 7, 7, 7, 7, 7, 7, 7650, 7650, 7651, 7, 7, 7, 8239, 7718, 7718, 7, 7, 7, 0, 7721, 0, 0, 8239, 8239, 7719, 8481, 8481, 7720, 7733, 7733, 7, 7, 7, 0, 7736, 0, 0, 8239, 8239, 7734, 7720, 7720, 7735, 7734, 7735, 7, 7, 7, 7, 7, 7, 7720, 7757, 7757, 7, 7, 7, 0, 7760, 0, 0, 8481, 8481, 7758, 7719, 7719, 7759, 7758, 7759, 7, 7, 7, 7, 7, 7, 7719, 7719, 7720, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 8537, 8537, 7, 7, 7, 8537, 1, 1, 7, 7, 7, 8239, 7805, 7805, 7, 7, 7, 0, 7808, 0, 0, 8239, 8239, 7806, 8500, 8500, 7807, 7820, 7820, 7, 7, 7, 0, 7823, 0, 0, 8239, 8239, 7821, 7807, 7807, 7822, 7821, 7822, 7, 7, 7, 7, 7, 7, 7807, 7844, 7844, 7, 7, 7, 0, 7847, 0, 0, 8500, 8500, 7845, 7806, 7806, 7846, 7845, 7846, 7, 7, 7, 7, 7, 7, 7806, 7806, 7807, 7, 7, 7, 8239, 8239, 774, 7, 7, 7, 774, 7880, 7880, 7, 7, 7, 0, 7882, 0, 7881, 7881, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8, 8, 7, 7, 7, 8, 1, 1, 7, 7, 7, 8, 8, 774, 7, 7, 7, 8, 8170, 8170, 7, 7, 7, 0, 8173, 8354, 8239, 8179, 8179, 7, 7, 7, 0, 8182, 0, 0, 8188, 8188, 7, 7, 7, 0, 8191, 0, 0, 8172, 8172, 8189, 8, 8, 8190, 8189, 8190, 7, 7, 7, 7, 7, 7, 8180, 8, 8, 8181, 8215, 8215, 7, 7, 7, 0, 8218, 0, 0, 8171, 8171, 8216, 8181, 8181, 8217, 8216, 8217, 7, 7, 7, 7, 7, 7, 8181, 8180, 8181, 7, 7, 7, 0, 0, 8545, 8545, 7, 7, 7, 3, 8252, 8252, 7, 7, 7, 0, 8254, 1, 8253, 8253, 7, 7, 7, 4, 8538, 8538, 7, 7, 7, 3, 8272, 8272, 7, 7, 7, 0, 8274, 1, 8273, 8273, 7, 7, 7, 4, 8539, 8539, 7, 7, 7, 3, 8292, 8292, 7, 7, 7, 0, 8294, 1, 8293, 8293, 7, 7, 7, 4, 8553, 8553, 7, 7, 7, 3, 8312, 8312, 7, 7, 7, 0, 8314, 1, 8313, 8313, 7, 7, 7, 4, 8548, 8548, 7, 7, 7, 3, 8332, 8332, 7, 7, 7, 0, 8334, 1, 8333, 8333, 7, 7, 7, 4, 8346, 8346, 7, 7, 7, 0, 8348, -1, 8347, 8347, 7, 7, 7, 0, 8554, 8554, 7, 7, 7, 3, 8366, 8366, 7, 7, 7, 0, 8368, 1, 8367, 8367, 7, 7, 7, 4, 8555, 8555, 7, 7, 7, 3, 8386, 8386, 7, 7, 7, 0, 8388, 1, 8387, 8387, 7, 7, 7, 4, 8548, 8548, 7, 7, 7, 3, 8406, 8406, 7, 7, 7, 0, 8408, 1, 8407, 8407, 7, 7, 7, 4, 8559, 8559, 7, 7, 7, 3, 8426, 8426, 7, 7, 7, 0, 8428, 1, 8427, 8427, 7, 7, 7, 4, 8547, 8547, 7, 7, 7, 3, 8446, 8446, 7, 7, 7, 0, 8448, 1, 8447, 8447, 7, 7, 7, 4, 8460, 8460, 7, 7, 7, 0, 8462, -1, 8461, 8461, 7, 7, 7, 0, 132, 5, 9, 75, 77, 13, 15, -32746, 150, -32744, 27, 92, 120, 93, 96, -32735, 34, 35, 228, 37, 99, 39, 168, -32727, 42, 106, -32721, 47, 178, 125, 56, 57, 250, -32707, 190, 0,
 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114, 111, 108, 101, 97, 80, 115, 87, 100, 116, 103, 58, 32, 67, 102, 110, 82, 105, 112, 117, 121, 104
};

char flag[] = "TSCTF-J{12345678901234567890123456}";
int cnt;
int main()
{
	unsigned int v8, v9, v10, v11;
	unsigned short v12;
	do
	{  
    	if(opcode[4] == 1)
    	{
        	opcode[4] = 0;
        	printf("print opcode[3](%c) ", opcode[3]); // 标记printf操作
        }
    	else if(opcode[6] == 1)
    	{
        	opcode[6] = 0;
        	opcode[5]= flag[cnt++];
        	printf("scanf opcode[5](%c) ", opcode[5]); // 标记scanf操作
        }
    	v8 = opcode[0]; cout << "IP=" << v8 <<" "; //输出IP
    	v9 = opcode[v8 + 1];
    	v10 = opcode[v8];
    	v11 = opcode[v8 + 2];
    	opcode[0] = v8 + 3; 
    	v12 = ~ (opcode[v10] | opcode[v9]); 
    	opcode[v11] = v12; 
    	opcode[1] = ((v12 << 1) | (v12 >> 15)) & 0xffff;
		printf("opcode[%d](%d) = NOR(opcode[%d](%d), opcode[%d](%d))  opcode[1] = %d\n\n", v11, opcode[v11], v10, opcode[v10], v9, opcode[v9], opcode[1]); // 输出NOR指令格式
    }while(opcode[0] != 0xFFFF);
}

0x03 开始硬刚

当然，在此之前还需要根据 hint 中的内容熟悉一下各种指令用 NOR 指令是怎么实现的

1
2
3
macro NOT a, r
	NOR a, a, r
endm
1
2
3
4
5
6
7
macro AND a, b, r
	local t1, t2
 	NOT a, t1
 	NOT b, t2
 	OR t1, t2, t1
 	NOT t1, r
endm
1
2
3
4
5
macro OR a, b, r
	local t
 	NOR a, b, t
 	NOT t, r
endm
1
2
3
4
5
6
7
8
macro XOR a, b, r
	local t1, t2
 	NOT b, t1
 	AND a, t1, t1
 	NOT a, t2
 	AND t2, b, t2
 	OR t1, t2, r
endm
1
2
3
macro MOV from, to
	OR from, from, to
endm
1
2
3
4
5
mem[IP] = OR(mem[from], mem[from])
// 另一种写法
macro JMP to_addr
	OR to_addr, to_addr, IP
endm
1
2
3
4
5
6
7
8
9
mem[IP] = OR(AND(to_addr, condition), AND(mem[IP], NOT(condition)))
// 另一种写法
macro BRANCH true_addr, false_addr, condition
	local t1, t2
 	AND true_addr, condition, t1
 	NOT condition, t2
 	AND false_addr, t2, t2
 	OR t1, t2, IP
endm

然后开始慢慢逆向路。。。

首先我们找到我们留下的 scanf 标识，发现就是我们构造的输入TSCTF-J。。。并且敏锐的发现 TS 的ASCII码分别是83, 84 那么很显然在接收到我们输入的flag之后，经过两次NOR操作，我们的输入被存放在opcode[8503], opcode[8504], opcode[8505]...处。

1666880281355

接着往下翻，在所有的scanf操作结束以后，加密操作就开始进行了

1666880684714

发现存入opcode[8537]后，开始对opcode[8503]进行加密操作，经过翻译发现加密操作共分为三种类型

第一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
opcode[7](65451) = NOR(opcode[8503](84), opcode[8503](84))  opcode[1] = 65367

opcode[8239](84) = NOR(opcode[7](65451), opcode[7](65451))  opcode[1] = 168 //0

opcode[7](65451) = NOR(opcode[8239](84), opcode[8239](84))  opcode[1] = 65367

opcode[8239](84) = NOR(opcode[7](65451), opcode[7](65451))  opcode[1] = 168

opcode[7](65367) = NOR(opcode[1](65199), opcode[1](65199))  opcode[1] = 65199

opcode[8239](168) = NOR(opcode[7](65367), opcode[7](65367))  opcode[1] = 336 //1

opcode[7](65367) = NOR(opcode[8239](168), opcode[8239](168))  opcode[1] = 65199

opcode[8239](168) = NOR(opcode[7](65367), opcode[7](65367))  opcode[1] = 336

opcode[7](65199) = NOR(opcode[1](64863), opcode[1](64863))  opcode[1] = 64863

opcode[8239](336) = NOR(opcode[7](65199), opcode[7](65199))  opcode[1] = 672 //2

opcode[7](65199) = NOR(opcode[8239](336), opcode[8239](336))  opcode[1] = 64863

opcode[8239](336) = NOR(opcode[7](65199), opcode[7](65199))  opcode[1] = 672

opcode[7](64863) = NOR(opcode[1](64191), opcode[1](64191))  opcode[1] = 64191

opcode[8239](672) = NOR(opcode[7](64863), opcode[7](64863))  opcode[1] = 1344 //3

opcode[7](64863) = NOR(opcode[8239](672), opcode[8239](672))  opcode[1] = 64191

opcode[8239](672) = NOR(opcode[7](64863), opcode[7](64863))  opcode[1] = 1344

opcode[7](64191) = NOR(opcode[1](62847), opcode[1](62847))  opcode[1] = 62847

opcode[8239](1344) = NOR(opcode[7](64191), opcode[7](64191))  opcode[1] = 2688 //4

opcode[7](64191) = NOR(opcode[8239](1344), opcode[8239](1344))  opcode[1] = 62847

opcode[8239](1344) = NOR(opcode[7](64191), opcode[7](64191))  opcode[1] = 2688

opcode[7](62847) = NOR(opcode[1](60159), opcode[1](60159))  opcode[1] = 60159

opcode[8239](2688) = NOR(opcode[7](62847), opcode[7](62847))  opcode[1] = 5376 //5

opcode[7](62847) = NOR(opcode[8239](2688), opcode[8239](2688))  opcode[1] = 60159

opcode[8239](2688) = NOR(opcode[7](62847), opcode[7](62847))  opcode[1] = 5376

opcode[7](60159) = NOR(opcode[1](54783), opcode[1](54783))  opcode[1] = 54783

opcode[8239](5376) = NOR(opcode[7](60159), opcode[7](60159))  opcode[1] = 10752 //6

opcode[7](60159) = NOR(opcode[8239](5376), opcode[8239](5376))  opcode[1] = 54783

opcode[8239](5376) = NOR(opcode[7](60159), opcode[7](60159))  opcode[1] = 10752

opcode[7](54783) = NOR(opcode[1](44031), opcode[1](44031))  opcode[1] = 44031

opcode[8239](10752) = NOR(opcode[7](54783), opcode[7](54783))  opcode[1] = 21504 //7

opcode[7](54783) = NOR(opcode[8239](10752), opcode[8239](10752))  opcode[1] = 44031

opcode[8239](10752) = NOR(opcode[7](54783), opcode[7](54783))  opcode[1] = 21504

opcode[7](44031) = NOR(opcode[1](22527), opcode[1](22527))  opcode[1] = 22527

opcode[8239](21504) = NOR(opcode[7](44031), opcode[7](44031))  opcode[1] = 43008 //8

opcode[7](44031) = NOR(opcode[8239](21504), opcode[8239](21504))  opcode[1] = 22527

opcode[8239](21504) = NOR(opcode[7](44031), opcode[7](44031))  opcode[1] = 43008

opcode[7](22527) = NOR(opcode[1](45054), opcode[1](45054))  opcode[1] = 45054

opcode[8239](43008) = NOR(opcode[7](22527), opcode[7](22527))  opcode[1] = 20481 //9

opcode[7](22527) = NOR(opcode[8239](43008), opcode[8239](43008))  opcode[1] = 45054

opcode[8239](43008) = NOR(opcode[7](22527), opcode[7](22527))  opcode[1] = 20481

opcode[7](45054) = NOR(opcode[1](24573), opcode[1](24573))  opcode[1] = 24573

opcode[8239](20481) = NOR(opcode[7](45054), opcode[7](45054))  opcode[1] = 40962 //10

opcode[7](45054) = NOR(opcode[8239](20481), opcode[8239](20481))  opcode[1] = 24573

opcode[8239](20481) = NOR(opcode[7](45054), opcode[7](45054))  opcode[1] = 40962

opcode[7](24573) = NOR(opcode[1](49146), opcode[1](49146))  opcode[1] = 49146

opcode[8239](40962) = NOR(opcode[7](24573), opcode[7](24573))  opcode[1] = 16389 //11

opcode[7](24573) = NOR(opcode[8239](40962), opcode[8239](40962))  opcode[1] = 49146

opcode[8239](40962) = NOR(opcode[7](24573), opcode[7](24573))  opcode[1] = 16389

opcode[7](49146) = NOR(opcode[1](32757), opcode[1](32757))  opcode[1] = 32757

opcode[8239](16389) = NOR(opcode[7](49146), opcode[7](49146))  opcode[1] = 32778 //12

opcode[7](49146) = NOR(opcode[8239](16389), opcode[8239](16389))  opcode[1] = 32757

opcode[8239](16389) = NOR(opcode[7](49146), opcode[7](49146))  opcode[1] = 32778

opcode[7](32757) = NOR(opcode[1](65514), opcode[1](65514))  opcode[1] = 65514

opcode[8239](32778) = NOR(opcode[7](32757), opcode[7](32757))  opcode[1] = 21 //13

opcode[7](32757) = NOR(opcode[8239](32778), opcode[8239](32778))  opcode[1] = 65514

opcode[8239](32778) = NOR(opcode[7](32757), opcode[7](32757))  opcode[1] = 21

opcode[7](65514) = NOR(opcode[1](65493), opcode[1](65493))  opcode[1] = 65493

opcode[8239](21) = NOR(opcode[7](65514), opcode[7](65514))  opcode[1] = 42 //14

opcode[7](65514) = NOR(opcode[8239](21), opcode[8239](21))  opcode[1] = 65493

opcode[8239](21) = NOR(opcode[7](65514), opcode[7](65514))  opcode[1] = 42

opcode[7](65493) = NOR(opcode[1](65451), opcode[1](65451))  opcode[1] = 65451

opcode[8239](42) = NOR(opcode[7](65493), opcode[7](65493))  opcode[1] = 84 //15

opcode[7](63865) = NOR(opcode[1667](1670), opcode[1667](1670))  opcode[1] = 62195

opcode[0](1670) = NOR(opcode[7](63865), opcode[7](63865))  opcode[1] = 3340 // opcode[0] = opcode[1667]

opcode[1668](65493) = NOR(opcode[8239](42), opcode[8239](42))  opcode[1] = 65451 // opcode[1668] = NOT(opcode[8239])

opcode[1669](65493) = NOR(opcode[8492](42), opcode[8492](42))  opcode[1] = 65451 // opcode[1669] = NOT(opcode[8492])

opcode[7](63850) = NOR(opcode[1682](1685), opcode[1682](1685))  opcode[1] = 62165

opcode[0](1685) = NOR(opcode[7](63850), opcode[7](63850))  opcode[1] = 3370 //opcode[0] = opcode[1682]

opcode[1683](65493) = NOR(opcode[8239](42), opcode[8239](42))  opcode[1] = 65451 

opcode[1684](42) = NOR(opcode[1669](65493), opcode[1669](65493))  opcode[1] = 84 

opcode[7](0) = NOR(opcode[1683](65493), opcode[1684](42))  opcode[1] = 0

opcode[7](65535) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 65535 

opcode[1669](0) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 0 // opcode[1669] = AND(opcode[8239], NOT(opcode[8492])) = 0

opcode[7](63826) = NOR(opcode[1706](1709), opcode[1706](1709))  opcode[1] = 62117 

opcode[0](1709) = NOR(opcode[7](63826), opcode[7](63826))  opcode[1] = 3418 //opcode[1709] = 0

opcode[1707](65493) = NOR(opcode[8492](42), opcode[8492](42))  opcode[1] = 65451 // opcode[1707] = NOT(opcode[8492])

opcode[1708](42) = NOR(opcode[1668](65493), opcode[1668](65493))  opcode[1] = 84 // opcode[1708] = NOT(opcode[1668])

opcode[7](0) = NOR(opcode[1707](65493), opcode[1708](42))  opcode[1] = 0

opcode[7](65535) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 65535

opcode[1668](0) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 0 // opcode[1668] = AND(NOT(opcode[8492], opcode[8239]) = 0

opcode[7](65535) = NOR(opcode[1668](0), opcode[1669](0))  opcode[1] = 65535

opcode[8239](0) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 0 //opcode[8239] = OR(opcode[1668], opcode[1669])

opcode[7](65535) = NOR(opcode[8239](0), opcode[774](0))  opcode[1] = 65535

opcode[774](0) = NOR(opcode[7](65535), opcode[7](65535))  opcode[1] = 0 //opcode[774] = OR(opcode[774], opcode[8239]

发现是把单个字节拿出来，存进opcode[8329]中，对其 ASCII 值进行 15 次循环左移操作，再和opcode[8942]进行比较

据此写出第一个解密算法

1
2
3
4
5
6
7
8
9
for(int i = 0; i < 14; i++)
	{
		int x = 15;
		while(x--)
		{
			enc[i] = ((enc[i] >> 1)|(enc[i] << 15)) & 0xffff;
		}
		printf("%c ", enc[i]);
	}

结合之前的分析，发现再每一次加密结束以后，会进行一次 Branch和一次JMP，其实可以不用管，我们只需要大胆猜测哪些是加密算法部分，然后利用这些重合的分支和跳转指令来区分每一次加密操作即可。

此时已是半夜两点半，做到此处的我以为所有的加密算法都是这样写的，还一度十分兴奋

1666881304120

第二种

按照第一种加密逻辑找了9个以后，我发现从第10位开始加密算法变了，tnnd

1666881390659

好死，只能按照之前的方法一步步翻译然后接着分析其加密方式，通过变化测试flag（这里说起来简单。。。）我发现opcode[8470], opcode[8479]是关键数据，因为不随测试flag而改变，opcode[8513]为输入，opcode[8239]更像是中间结果。

1666881604086

通过分析，我发现这一步的加密其实就是opcode[8513] ^ opcode[8470] == opcode[8479]，直接找到这几个数据然后异或回去即可。

第三种

正当我以为即将大功告成时，接下来一位的加密算法又不一样了，经过反复观察，发现后面的几位用的是第一种加密，捏麻麻的😅，这玩意还是几种加密方法混着用是吧。

然后在opcode[8517]中，又出现了一种新加密方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
opcode[7](65480) = NOR(opcode[8517](55), opcode[8517](55))  opcode[1] = 65425

opcode[8517](55) = NOR(opcode[7](65480), opcode[7](65480))  opcode[1] = 110

opcode[7](65425) = NOR(opcode[1](65315), opcode[1](65315))  opcode[1] = 65315

opcode[8239](110) = NOR(opcode[7](65425), opcode[7](65425))  opcode[1] = 220

opcode[7](60619) = NOR(opcode[4913](4916), opcode[4913](4916))  opcode[1] = 55703

opcode[0](4916) = NOR(opcode[7](60619), opcode[7](60619))  opcode[1] = 9832

opcode[4914](65425) = NOR(opcode[8239](110), opcode[8239](110))  opcode[1] = 65315

opcode[4915](65345) = NOR(opcode[8502](190), opcode[8502](190))  opcode[1] = 65155

opcode[7](60604) = NOR(opcode[4928](4931), opcode[4928](4931))  opcode[1] = 55673

opcode[0](4931) = NOR(opcode[7](60604), opcode[7](60604))  opcode[1] = 9862

opcode[4929](65425) = NOR(opcode[8239](110), opcode[8239](110))  opcode[1] = 65315

opcode[4930](190) = NOR(opcode[4915](65345), opcode[4915](65345))  opcode[1] = 380

opcode[7](64) = NOR(opcode[4929](65425), opcode[4930](190))  opcode[1] = 128

opcode[7](65471) = NOR(opcode[7](65471), opcode[7](65471))  opcode[1] = 65407

opcode[4915](64) = NOR(opcode[7](65471), opcode[7](65471))  opcode[1] = 128

opcode[7](60580) = NOR(opcode[4952](4955), opcode[4952](4955))  opcode[1] = 55625

opcode[0](4955) = NOR(opcode[7](60580), opcode[7](60580))  opcode[1] = 9910

opcode[4953](65345) = NOR(opcode[8502](190), opcode[8502](190))  opcode[1] = 65155

opcode[4954](110) = NOR(opcode[4914](65425), opcode[4914](65425))  opcode[1] = 220

opcode[7](144) = NOR(opcode[4953](65345), opcode[4954](110))  opcode[1] = 288

opcode[7](65391) = NOR(opcode[7](65391), opcode[7](65391))  opcode[1] = 65247

opcode[4914](144) = NOR(opcode[7](65391), opcode[7](65391))  opcode[1] = 288

opcode[7](65327) = NOR(opcode[4914](144), opcode[4915](64))  opcode[1] = 65119

opcode[8239](208) = NOR(opcode[7](65327), opcode[7](65327))  opcode[1] = 416

opcode[7](65280) = NOR(opcode[8239](208), opcode[774](127))  opcode[1] = 65025

opcode[774](255) = NOR(opcode[7](65280), opcode[7](65280))  opcode[1] = 510

好在这里的加密算法还是很简单

1666882242995

一眼秒出opcode[8514] * 2 == opcode[8239]，多次测试证实了猜想。

0x04 脚本解密

于是开始一个一个ctrl+F找每一位的加密方式，并且把特征数据dump出来，最终写出exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
using namespace std;
unsigned short enc[] = {42, 32809, 32801, 42, 35, 32790, 37, 32829, 32809, 56, 32792, 34, 39, 32815};
int main()
{
	for(int i = 0; i < 14; i++)
	{
		int x = 15;
		while(x--)
		{
			enc[i] = ((enc[i] >> 1)|(enc[i] << 15)) & 0xffff;
		}
		printf("%c ", enc[i]);
	}cout << endl;
	printf("%c %c %c %c %c %c %c %c %c %c", (77 ^ 57), (9 ^ 92), (106 ^ 5), (77 ^ 125), (27 ^ 42), (13 ^ 99), (47 ^ 96), (15 ^ 120), (37 ^ 75), (15 ^ 93));cout << endl;
	printf("%c %c %c %c %c %c %c %c %c %c %c", 190/2, 228/2, 96/2, 132/2, 168/2, 190/2, 178/2, 190/2, 150/2, 96/2, 250/2);
}

运行以后在拼接起来（这里要记录每一个字符对应的加密操作，分个类）

1666885399216

得到flagTSCTF-J{StUp1D_r0BoT_0N1Y_KnOw_n0R}

祥云杯2022 - machine

golang逆向，用 VM 实现了一个栈机，先恢复一下符号表，然后 patch 一下主函数里面的 if 分支，把多余的全给nop掉即可得到反编译代码，虽然还是很恶心。

然后开始动态调试，看到有ReadFile，且附近有 code.in 的字符串，应该是初始的 opcde ，给dump出来

1668159695878

然后再看后面的加密操作，发现是个栈机放个简单的例子

1668160471567

按照这种方法一个一个case给翻译出来，然后写成c语言代码（这里直接放 iPlayForSG👴的代码），跑出来然后直接O2优化编译一下就能拿angr梭了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>

#define maxn 30005

long long c;
//long long opcodes[maxn], stack[maxn], tempdir[9];
unsigned long long stack[maxn], tempdir[9];
unsigned long long opcodes[maxn] = {太长了自己dump吧}; 
int cnt, cnt_opcodes = 28894, top;
long long op, op1, op2;
int main()
{
	freopen("my_vm", "w", stdout);
	while (cnt_opcodes >= -1)
	{
		--cnt_opcodes;
		op = opcodes[cnt];
		switch (op)
		{
			case 0:
				printf("stack[top++] = %llu;\n", opcodes[cnt + 1]); 
				stack[top++] = opcodes[cnt + 1];
				cnt += 2;
				break;
				
			case 1:
				printf("stack[top++] = rg[%u];\n", opcodes[cnt + 1]);
				stack[top++] = tempdir[opcodes[cnt + 1]];
				cnt += 2;
				break;
				
			case 2:
				printf("rg[%u] = stack[top - 1];\n--top;\n", opcodes[cnt + 1]);
				tempdir[opcodes[cnt + 1]] = stack[top - 1];
				--top;
				cnt += 2;
				break;
				
			case 3:
				printf("stack[top - 2] = stack[top - 1] + stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 + op2) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 4:
				printf("stack[top - 2] = stack[top - 1] - stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 - op2) & (0xFFFFFFFFFFFFFFFF); 
				cnt += 1;
				break;
				
			case 5:
				printf("stack[top - 2] = stack[top - 1] * stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 * op2) & (0xFFFFFFFFFFFFFFFF); 
				cnt += 1;
				break;
				
			case 6:
				printf("stack[top - 2] = stack[top - 1] / stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 / op2) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 7:
				printf("stack[top - 2] = stack[top - 1] ^ stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 ^ op2) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 8:
				printf("stack[top - 2] = stack[top - 1] << stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				if (op1 >= 64) stack[top++] = 0;
				else stack[top++] = (op1 << op2) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 9:
				printf("stack[top - 2] = stack[top - 1] >> stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				if (op1 >= 64) stack[top++] = 0;
				else stack[top++] = (op1 >> op2) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 10:
				printf("stack[top - 1] = ~ stack[top - 1];\n");
				op = stack[top - 1];
				--top;
				stack[top++] = (~op) & (0xFFFFFFFFFFFFFFFF);
				cnt += 1;
				break;
				
			case 11:
				printf("stack[top - 2] = stack[top - 1] & stack[top - 2];\n--top;\n");
				op1 = stack[top - 1];
				op2 = stack[top - 2];
				top -= 2;
				stack[top++] = (op1 & op2);
				cnt += 1;
				break;
				
			case 12:
				printf("stack[top++] = getchar();\n");
//				scanf("%lld", &c);
				stack[top++] = c;
				cnt += 1;
				break;
				
			case 13:
				printf("putchar(\'%c\');\n", opcodes[cnt + 1]);
//				printf("%c", (char)opcodes[cnt + 1]);
				cnt += 2;
				break;
				
			case 14:
				printf("if(stack[--top] != 0) {printf(\"Fail\\n\"); return 0;}\n");
				op = stack[top - 1];
				--top;
//				if (op)
//				{
//					printf("Fail\n");
//					return 0;
//				}
				cnt += 1;
				break;
		}
	}
	return 0;
}

得到flag{734f1698a5775ec26cd2e11ed4791e77}