#define BC2 cout << (((long long)v[x].s[k] + v[y].s[k] - v[z].s[k] - v[v[z].f[0]].s[k]) % mod + mod) % mod << '\n';
#define BC1 ios::sync_with_stdio(0);
#define BC0 v[y].e.push_back(x);
#define BBF v[x].e.push_back(y),
#define BBE v[v[j].f[i]].f[i];
#define BBD cout.tie(0);
#define BBC ___0xffff___
#define BBB cin.tie(0),
#define BBA vector<int>
#define BB9 0x6301d76f
#define BB8 0x6303292b
#define BB7 v[x].f[i],
#define BB6 998244353,
#define BB5 v[x].f[0];
#define BB4 (v[f].s[i]
#define BB3 (v[x].f[i]
#define BB2 v[y].f[i])
#define BB1 v[y].f[i];
#define BB0 v[x].s[i]
#define BAF namespace
#define BAE v[x].f[0]
#define BAD ((v[y].d
#define BAC v[j].f[i
#define BAB swap(x,
#define BAA v[x].d)
#define BA9 v[x].e)
#define BA8 v[y].d)
#define BA7 (v[x].d
#define BA6 dfs(int
#define BA5 LCA(int
#define BA4 v[f].d
#define BA3 LCA(x,
#define BA2 return
#define BA1 dfs(0,
#define BA0 v[x].d
#define B9F dfs(x,
#define B9E struct
#define B9D printf
#define B9C s[K];
#define B9B (m--)
#define B9A const
#define B99 f[L],
#define B98 using
#define B97 v[N];
#define B96 while
#define B95 0x6f
#define B94 0x70
#define B93 0x73
#define B92 0x74
#define B91 0xca
#define B90 0xa7
#define B8F 0xa8
#define B8E 0xaa
#define B8D 0xb1
#define B8C 0xb4
#define B8B 0xb5
#define B8A 0xb7
#define B89 0xb9
#define B88 0xbc
#define B87 0xc1
#define B86 0xc2
#define B85 0xc3
#define B84 0xc6
#define B83 0xc7
#define B82 0xc8
#define B81 0x2f
#define B80 0xcb
#define B7F 0xcc
#define B7E 0xce
#define B7D 0xcf
#define B7C 0xd0
#define B7B 0xd1
#define B7A 0xd2
#define B79 0xd3
#define B78 0xd4
#define B77 0xd5
#define B76 0xd7
#define B75 0xda
#define B74 0xde
#define B73 0xdf
#define B72 0xe7
#define B71 0xeb
#define B70 0xf7
#define B6F 0xf8
#define B6E 0xfa
#define B6D 0xfd
#define B6C else
#define B6B long
#define B6A main
#define B69 mod;
#define B68 0x78
#define B67 "%s"
#define B66 "\n"
#define B65 std;
#define B64 (int
#define B63 char
#define B62 time
#define B61 ++i)
#define B60 ++j)
#define B5F --i)
#define B5E 0xe8
#define B5D C();
#define B5C 0x20
#define B5B 0x23
#define B5A 0x2d
#define B59 0x2e
#define B58 0x3a
#define B57 0x61
#define B56 0x62
#define B55 0x63
#define B54 0x64
#define B53 0x65
#define B52 0x66
#define B51 0x68
#define B50 void
#define B4F 0x6d
#define B4E 22,
#define B4D 0xa
#define B4C -1,
#define B4B for
#define B4A i);
#define B49 int
#define B48 51;
#define B47 1),
#define B46 3e5
#define B45 cin
#define B44 mod
#define B43 0x0
#define B42 C()
#define B41 y);
#define B40 K;
#define B3F L;
#define B3E &&
#define B3D d,
#define B3C ()
#define B3B (i
#define B3A (j
#define B39 e;
#define B38 0;
#define B37 f)
#define B36 f,
#define B35 !=
#define B34 1)
#define B33 1;
#define B32 if
#define B31 1]
#define B30 5,
#define B2F j)
#define B2E k,
#define B2D k;
#define B2C <=
#define B2B m,
#define B2A m;
#define B29 ==
#define B28 >=
#define B27 >>
#define B26 n,
#define B25 x)
#define B24 x,
#define B23 y)
#define B22 n;
#define B21 y;
#define B20 >
#define B1F L
#define B1E =
#define B1D -
#define B1C ,
#define B1B i
#define B1A N
#define B19 [
#define B18 ;
#define B17 ]
#define B16 +
#define B15 j
#define B14 a
#define B13 b
#define B12 c
#define B11 *
#define B10 )
#define BF (
#define BE &
#define BD %
#define BC <
#define BB d
#define BA ?
#define B9 x
#define B8 :
#define B7 0
#define B6 y
#define B5 E
#define B4 e
#define B3 K
#define B2 z
#define B1 {
#define B0 }
#include <time.h>
#include <bits/stdc++.h>
#define BC3 B98 BAF B65 B9A B49 B1A B1E B46 B16 B30
#define BC4 B1F B1E B4E B44 B1E BB6 B3 B1E B48 B9E
#define BC5 B5 B1 B49 B99 BB B1E B4C B9C BBA B39
#define BC6 B0 B97 B49 B26 B2B B2E B24 B21 B50 BA6
#define BC7 B36 B49 B25 B1 BAE B1E B36 BA0 B1E BA4
#define BC8 B16 B33 B6B B6B B15 B1E B33 B4B B64 B1B
#define BC9 B1E B33 B1B BC B40 B61 B1 B15 B1E B3A
#define BCA B11 BAA BD B69 BB0 B1E BB4 B16 B2F BD
#define BCB B69 B0 B4B B64 B1B B8 BA9 B1 B32 B3B
#define BCC B35 B37 B1 B9F B4A B0 B0 B0 B50 B42
#define BCD B1 B4B B64 B1B B1E B38 B1B BC B1F B1D
#define BCE B33 B61 B1 B4B B64 B15 B1E B33 B15 B2C
#define BCF B22 B60 B1 BAC B16 B31 B1E BBE B0 B0
#define BD0 B0 B49 BA5 B24 B49 B23 B1 B32 BA7 B20
#define BD1 BA8 B1 BAB B41 B0 B4B B64 B1B B1E B38
#define BD2 B1B BC B3F B61 B1 B32 BAD B1D BAA B27
#define BD3 B1B BE B34 B1 B6 B1E BB1 B0 B0 B4B
#define BD4 B64 B1B B1E B1F B1D B33 B1B B28 B38 B5F
#define BD5 B1 B32 BB3 B35 BB2 B1 B9 B1E BB7 B6
#define BD6 B1E BB1 B0 B0 BA2 B9 B29 B6 BA B9
#define BD7 B8 BB5 B0 B49 BBC B3C B1 BC1 BBB BBD
#define BD8 B45 B27 B22 B4B B64 B1B B1E B33 B1B BC
#define BD9 B22 B61 B1 B45 B27 B9 B27 B21 BBF BC0
#define BDA B0 BA1 B47 B5D B45 B27 B2A B96 B9B B1
#define BDB B45 B27 B9 B27 B6 B27 B2D B49 B2 B1E
#define BDC BA3 B41 BC2 B0 BA2 B38 B0 B49 B6A BF
#define BDD B10 B1 B32 BF B62 BF B7 B10 B20 BB9
#define BDE B3E B62 BF B7 B10 BC BB8 B10 B1 BBC
#define BDF BF B10 B18 B0 B6C B1 B63 B14 B19 B17
#define BE0 B1E B1 BF B63 B10 B5B B1C BF B63 B10
#define BE1 B5C B1C BF B63 B10 B8C B1C BF B63 B10
#define BE2 B6E B1C BF B63 B10 B86 B1C BF B63 B10
#define BE3 B71 B1C BF B63 B10 B91 B1C BF B63 B10
#define BE4 B8D B1C BF B63 B10 B7C B1C BF B63 B10
#define BE5 B90 B1C BF B63 B10 B89 B1C BF B63 B10
#define BE6 B6D B1C BF B63 B10 B84 B1C BF B63 B10
#define BE7 B75 B1C BF B63 B10 B7A B1C BF B63 B10
#define BE8 B7B B1C BF B63 B10 B7E B1C BF B63 B10
#define BE9 B74 B1C BF B63 B10 B8A B1C BF B63 B10
#define BEA B8F B1C BF B63 B10 B78 B1C BF B63 B10
#define BEB B80 B1C BF B63 B10 B7C B1C BF B63 B10
#define BEC B7C B1C BF B63 B10 B5C B1C BF B63 B10
#define BED B5B B1C BF B63 B10 B43 B0 B18 B63 B13
#define BEE B19 B17 B1E B1 BF B63 B10 B5B B1C BF
#define BEF B63 B10 B5C B1C BF B63 B10 B82 B1C BF
#define BF0 B63 B10 B72 B1C BF B63 B10 B7C B1C BF
#define BF1 B63 B10 B5E B1C BF B63 B10 B88 B1C BF
#define BF2 B63 B10 B7F B1C BF B63 B10 B7C B1C BF
#define BF3 B63 B10 B6F B1C BF B63 B10 B91 B1C BF
#define BF4 B63 B10 B89 B1C BF B63 B10 B79 B1C BF
#define BF5 B63 B10 B85 B1C BF B63 B10 B83 B1C BF
#define BF6 B63 B10 B71 B1C BF B63 B10 B87 B1C BF
#define BF7 B63 B10 B8E B1C BF B63 B10 B7D B1C BF
#define BF8 B63 B10 B8B B1C BF B63 B10 B76 B1C BF
#define BF9 B63 B10 B70 B1C BF B63 B10 B77 B1C BF
#define BFA B63 B10 B73 B1C BF B63 B10 B5C B1C BF
#define BFB B63 B10 B5B B1C BF B63 B10 B43 B0 B18
#define BFC B63 B12 B19 B17 B1E B1 BF B63 B10 B5A
#define BFD B1C BF B63 B10 B5A B1C BF B63 B10 B5C
#define BFE B1C BF B63 B10 B51 B1C BF B63 B10 B92
#define BFF B1C BF B63 B10 B92 B1C BF B63 B10 B94
#define B100 B1C BF B63 B10 B93 B1C BF B63 B10 B58
#define B101 B1C BF B63 B10 B81 B1C BF B63 B10 B81
#define B102 B1C BF B63 B10 B55 B1C BF B63 B10 B95
#define B103 B1C BF B63 B10 B54 B1C BF B63 B10 B53
#define B104 B1C BF B63 B10 B52 B1C BF B63 B10 B95
#define B105 B1C BF B63 B10 B68 B1C BF B63 B10 B59
#define B106 B1C BF B63 B10 B92 B1C BF B63 B10 B57
#define B107 B1C BF B63 B10 B95 B1C BF B63 B10 B56
#define B108 B1C BF B63 B10 B57 B1C BF B63 B10 B95
#define B109 B1C BF B63 B10 B59 B1C BF B63 B10 B55
#define B10A B1C BF B63 B10 B95 B1C BF B63 B10 B4F
#define B10B B1C BF B63 B10 B5C B1C BF B63 B10 B5A
#define B10C B1C BF B63 B10 B5A B1C BF B63 B10 B4D
#define B10D B1C BF B63 B10 B43 B0 B18 B63 BB B19
#define B10E B17 B1E B67 B18 B63 B4 B19 B17 B1E B66
#define B10F B18 B9D BF B3D B14 B10 B18 B9D BF B4
#define B110 B10 B18 B9D BF B3D B13 B10 B18 B9D BF
#define B111 B4 B10 B18 B9D BF B3D B12 B10 B18 B0
#define B112 BA2 B38 B0 
#define B113 BC3 BC4 BC5 BC6 BC7 BC8 BC9 BCA BCB BCC
#define B114 BCD BCE BCF BD0 BD1 BD2 BD3 BD4 BD5 BD6
#define B115 BD7 BD8 BD9 BDA BDB BDC BDD BDE BDF BE0
#define B116 BE1 BE2 BE3 BE4 BE5 BE6 BE7 BE8 BE9 BEA
#define B117 BEB BEC BED BEE BEF BF0 BF1 BF2 BF3 BF4
#define B118 BF5 BF6 BF7 BF8 BF9 BFA BFB BFC BFD BFE
#define B119 BFF B100 B101 B102 B103 B104 B105 B106 B107 B108
#define B11A B109 B10A B10B B10C B10D B10E B10F B110 B111 B112
#define B11B B113 B114 B115 B116 B117 B118 B119 B11A 
#define B11C(__FOX__) __FOX__
B11C(B11B)