1. typedef long long int ll;
2. typedef long double ld;
3. typedef short int sh;
4.  
5. inline void readI(int *i)
6. {
7.         register int t=0;
8.         register char z=getchar();
9.         int znak=1;
10.         if (z=='-')
11.         {
12.                 znak=-1;
13.         }
14.         while ((z<'0') || ('9'<z))
15.         {
16.                 z=getchar();
17.                 if (z=='-')
18.                 {
19.                         znak=-1;
20.                 }
21.         }
22.         while (('0'<=z) && (z<='9'))
23.         {
24.                 t=(t<<3)+(t<<1)+z-'0';
25.                 z=getchar();
26.         }
27.         *i=(t*znak);
28. }
29. inline void readUI(int *i)
30. {
31.         register int t=0;
32.         register char z=getchar();
33.         while ((z<'0') || ('9'<z))
34.         {
35.                 z=getchar();
36.         }
37.         while (('0'<=z) && (z<='9'))
38.         {
39.                 t=(t<<3)+(t<<1)+z-'0';
40.                 z=getchar();
41.         }
42.         *i=t;
43. }
44. inline void readL(ll *l)
45. {
46.         register ll t=0;
47.         register char z=getchar();
48.         int znak=1;
49.         if (z=='-')
50.         {
51.                 znak*=-1;
52.         }
53.         while ((z<'0') || ('9'<z))
54.         {
55.                 z=getchar();
56.                 if (z=='-')
57.                 {
58.                         znak=-1;
59.                 }
60.         }
61.         while (('0'<=z) && (z<='9'))
62.         {
63.                 t=(t<<3)+(t<<1)+z-'0';
64.                 z=getchar();
65.         }
66.         *l=(t*znak);
67. }
68. inline void readUL(ll *l)
69. {
70.         register ll t=0;
71.         register char z=getchar();
72.         while ((z<'0') || ('9'<z))
73.         {
74.                 z=getchar();
75.         }
76.         while (('0'<=z) && (z<='9'))
77.         {
78.                 t=(t<<3)+(t<<1)+z-'0';
79.                 z=getchar();
80.         }
81.         *l=t;
82. }
83. inline void writeL(ll l)
84. {
85.         if (l==0)
86.         {
87.                 putchar(48);
88.         }
89.         else
90.         {
91.                 if (l<0)
92.                 {
93.                    l*=-1;
94.                    putchar(45);
95.                 }
96.                 int _tab[21];
97.                 int wsk=0;
98.                 while (l>0)
99.                 {
100.                         ++wsk;
101.                         _tab[wsk]=(l%10)+48;
102.                         l/=10;
103.                 }
104.                 for (int j=wsk; j>=1; --j)
105.                 {
106.                         putchar(_tab[j]);
107.                 }
108.         }
109. }
110. inline void writeS(string s)
111. {
112.         int l=s.length();
113.         for (int i=0; i<l; ++i)
114.         {
115.                 putchar(s[i]);
116.         }
117. }