codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

772.md (51080B)


      1 Source: https://codeforces.com/blog/entry/51598
      2 
      3 **Viscious Keyboard**
      4 
      5 Tutorial is loading...
      6 
      7 **example code 1**
      8 
      9 ```
     10 print (lambda s: max((s[:i] + x + s[i+1:]).count("VK") for x in "VK" for i in range(len(s))))(raw_input())
     11 ```
     12 
     13 **example code 2**
     14 
     15 ```
     16 print (lambda s: s.count("VK") + int(any(x*3 in "K" + s + "V" for x in "VK")))(raw_input())
     17 ```
     18 
     19 **Valued Keys**
     20 
     21 Tutorial is loading...
     22 
     23 **example code**
     24 
     25 ```
     26 x,y = raw_input(), raw_input()
     27 print all(a>=b for a,b in zip(x,y)) * y or "-1"
     28 ```
     29 
     30 **Voltage Keepsake**
     31 
     32 Tutorial is loading...
     33 
     34 **example code (c++)**
     35 
     36 ```
     37 #include <stdio.h>
     38 #include <algorithm>
     39 #include <assert.h>
     40 using namespace std;
     41 typedef long long ll;
     42 typedef long double ld;
     43 // Adjust MAXN for bounds
     44 const ll MAXN=1e5+4;
     45 // MAXV is the max amount of time we can take
     46 const ld MAXV=1e18;
     47 ll a[MAXN],b[MAXN];
     48 ld exhaust[MAXN];
     49 int n;
     50 ll P;
     51 bool f(ld imid) {
     52 	ld needsum=0;
     53 	for (int i=0;i<n;i++) {
     54 		ld need=max(0.0L, (imid-exhaust[i])*a[i]);
     55 		needsum+=need;
     56 	}
     57 	ld supply=imid*P;
     58 	return supply>=needsum;
     59 }
     60 int main() 
     61 {
     62 	scanf("%d%lld",&n,&P);
     63 	for (int i=0;i<n;i++) {
     64 		scanf("%lld%lld",&a[i],&b[i]);
     65 	}
     66 	ll suma=0;
     67 	for (int i=0;i<n;i++) {
     68 		suma+=a[i];
     69 	}
     70 	if (P>=suma) {
     71 		printf("-1\n");
     72 		return 0;
     73 	}
     74 	for (int i=0;i<n;i++) {
     75 		exhaust[i]=((ld)b[i])/((ld)a[i]);
     76 	}
     77 	ld imin=0,imax=MAXV;
     78 	for (ll iter=0;iter<220;iter++) {
     79 		ld imid=(imin+imax)/2;
     80 		if (f(imid)) imin=imid;
     81 		else imax=imid;
     82 	}
     83 	if (imax>MAXV-100) printf("-1\n");
     84 	else printf("%.9f\n",(double)imin);
     85 }
     86 ```
     87 
     88 **Volatile Kite**
     89 
     90 Tutorial is loading...
     91 
     92 **example code (c++)**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96 using namespace std;
     97 #define sim template < class c
     98 #define ris return * this
     99 #define dor > debug & operator <<
    100 #define eni(x) sim > typename \
    101   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
    102 sim > struct rge {c b, e; };
    103 sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
    104 sim > auto dud(c* x) -> decltype(cerr << *x, 0);
    105 sim > char dud(...);
    106 struct debug {
    107 #ifdef LOCAL
    108 ~debug() { cerr << endl; }
    109 eni(!=) cerr << boolalpha << i; ris; }
    110 eni(==) ris << range(begin(i), end(i)); }
    111 sim, class b dor(pair < b, c > d) {
    112   ris << "(" << d.first << ", " << d.second << ")";
    113 }
    114 sim dor(rge<c> d) {
    115   *this << "[";
    116   for (auto it = d.b; it != d.e; ++it)
    117     *this << ", " + 2 * (it == d.b) << *it;
    118   ris << "]";
    119 }
    120 #else
    121 sim dor(const c&) { ris; }
    122 #endif
    123 };
    124 #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
    125 
    126 typedef long double ld;
    127 typedef long double ll;
    128 
    129 ld K(ld a) { return a * a; }
    130 
    131 struct P {
    132 	ll x, y;
    133 	void read() { cin >> x >> y; }
    134 	P operator + (P b) { return P{x + b.x, y + b.y}; }
    135 	P operator - (P b) { return P{x - b.x, y - b.y}; }
    136 	P operator * (ld/*ll*/ mul) { return P{x * mul, y * mul}; }
    137 	ll operator * (P b) { return x * b.y - y * b.x; }
    138 	ll dot(P b) { return x * b.x + y * b.y; }
    139 	ld len() { return sqrt(K(x) + K(y)); }
    140 	P lenTo(ld to) { return *this * (to / len()); }
    141 	ld dist(P & b) { return (*this - b).len(); }
    142 };
    143 
    144 struct L2 {
    145 	P one, two;
    146 	ld dist(P he) {
    147 		return abs((he - one) * (he - two)) / one.dist(two);
    148 	}
    149 };
    150 
    151 int main() {
    152 	int n;
    153 	cin >> n;
    154 	vector<P> points(n);
    155 	for(P & p : points)
    156 		p.read();
    157 	ld answer = 1e15;
    158 	for(int i = 0; i < n; ++i)
    159 		for(int j = 0; j < 2 * n; ++j)
    160 			if(abs(i - j) <= 2)
    161 				for(int k = 0; k < 2 * n; ++k)
    162 					if(abs(i - k) <= 2 && (int) set<int>{i % n, j % n, k % n}.size() == 3)
    163 						answer = min(answer, L2{points[i%n], points[j%n]}.dist(points[k%n]));
    164 	printf("%.10lf\n", (double) answer / 2);
    165 }
    166 ```
    167 
    168 **example code (java)**
    169 
    170 ```
    171 import java.io.OutputStream;
    172 import java.io.IOException;
    173 import java.io.InputStream;
    174 import java.io.OutputStream;
    175 import java.io.PrintWriter;
    176 import java.io.BufferedWriter;
    177 import java.io.Writer;
    178 import java.io.OutputStreamWriter;
    179 import java.util.InputMismatchException;
    180 import java.io.IOException;
    181 import java.io.InputStream;
    182 
    183 /**
    184  * Built using CHelper plug-in
    185  * Actual solution is at the top
    186  */
    187 public class Main {
    188     public static void main(String[] args) {
    189         InputStream inputStream = System.in;
    190         OutputStream outputStream = System.out;
    191         InputReader in = new InputReader(inputStream);
    192         OutputWriter out = new OutputWriter(outputStream);
    193         NonConvexPolygon solver = new NonConvexPolygon();
    194         solver.solve(1, in, out);
    195         out.close();
    196     }
    197 
    198     static class NonConvexPolygon {
    199         public void solve(int testNumber, InputReader in, OutputWriter out) {
    200             int n = in.nextInt();
    201             long[][] p = new long[n][2];
    202             for (int i = 0; i < n; i++) {
    203                 p[i][0] = in.nextInt();
    204                 p[i][1] = in.nextInt();
    205             }
    206             double ans = 1L << 60;
    207             for (int i = 0; i < n; i++) {
    208                 int prev = (i + n - 1) % n, next = (i + 1) % n;
    209                 ans = Math.min(ans, PointToSegmentDistance.pointToLineThroughTwoPointsDistance(
    210                         p[i][0], p[i][1], p[prev][0], p[prev][1], p[next][0], p[next][1]
    211                 ) / 2.0);
    212             }
    213             out.printf("%.10f\n", ans);
    214         }
    215 
    216     }
    217 
    218     static class Utils {
    219         public static double cross(Point a, Point b, Point c) {
    220             Point ab = new Point(b.x - a.x, b.y - a.y);
    221             Point ac = new Point(c.x - a.x, c.y - a.y);
    222             return ab.x * ac.y - ab.y * ac.x;
    223         }
    224 
    225     }
    226 
    227     static class PointToSegmentDistance {
    228         static double fastHypot(double x, double y) {
    229             return Math.sqrt(x * x + y * y);
    230         }
    231 
    232         public static double pointToLineThroughTwoPointsDistance(long x, long y, long ax, long ay, long bx, long by) {
    233             double t = Utils.cross(new Point(ax, ay), new Point(bx, by), new Point(x, y));
    234             return Math.abs(t / fastHypot(ax - bx, ay - by));
    235         }
    236 
    237     }
    238 
    239     static class Point implements Comparable<Point> {
    240         public double x;
    241         public double y;
    242         public double angle;
    243         public int idx;
    244 
    245         public Point(double x, double y) {
    246             this.x = x;
    247             this.y = y;
    248             angle = 0;
    249         }
    250 
    251         public Point(double x, double y, int idx) {
    252             this.x = x;
    253             this.y = y;
    254             this.idx = idx;
    255         }
    256 
    257         public int compareTo(Point other) {
    258             return x == other.x ? (int) Math.signum(y - other.y) : (int) Math.signum(x - other.x);
    259         }
    260 
    261     }
    262 
    263     static class OutputWriter {
    264         private final PrintWriter writer;
    265 
    266         public OutputWriter(OutputStream outputStream) {
    267             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    268         }
    269 
    270         public OutputWriter(Writer writer) {
    271             this.writer = new PrintWriter(writer);
    272         }
    273 
    274         public void printf(String format, Object... objects) {
    275             writer.printf(format, objects);
    276         }
    277 
    278         public void close() {
    279             writer.close();
    280         }
    281 
    282     }
    283 
    284     static class InputReader {
    285         private InputStream stream;
    286         private byte[] buf = new byte[1024];
    287         private int curChar;
    288         private int numChars;
    289 
    290         public InputReader(InputStream stream) {
    291             this.stream = stream;
    292         }
    293 
    294         public int read() {
    295             if (this.numChars == -1) {
    296                 throw new InputMismatchException();
    297             } else {
    298                 if (this.curChar >= this.numChars) {
    299                     this.curChar = 0;
    300 
    301                     try {
    302                         this.numChars = this.stream.read(this.buf);
    303                     } catch (IOException var2) {
    304                         throw new InputMismatchException();
    305                     }
    306 
    307                     if (this.numChars <= 0) {
    308                         return -1;
    309                     }
    310                 }
    311 
    312                 return this.buf[this.curChar++];
    313             }
    314         }
    315 
    316         public int nextInt() {
    317             int c;
    318             for (c = this.read(); isSpaceChar(c); c = this.read()) {
    319                 ;
    320             }
    321 
    322             byte sgn = 1;
    323             if (c == 45) {
    324                 sgn = -1;
    325                 c = this.read();
    326             }
    327 
    328             int res = 0;
    329 
    330             while (c >= 48 && c <= 57) {
    331                 res *= 10;
    332                 res += c - 48;
    333                 c = this.read();
    334                 if (isSpaceChar(c)) {
    335                     return res * sgn;
    336                 }
    337             }
    338 
    339             throw new InputMismatchException();
    340         }
    341 
    342         public static boolean isSpaceChar(int c) {
    343             return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    344         }
    345 
    346     }
    347 }
    348 ```
    349 
    350 **Vulnerable Kerbals**
    351 
    352 Tutorial is loading...
    353 
    354 **example code (c++)**
    355 
    356 ```
    357 #include <bits/stdc++.h>
    358 using namespace std;
    359 #define sim template < class c
    360 #define ris return * this
    361 #define dor > debug & operator <<
    362 #define eni(x) sim > typename \
    363   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
    364 sim > struct rge {c b, e; };
    365 sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
    366 sim > auto dud(c* x) -> decltype(cerr << *x, 0);
    367 sim > char dud(...);
    368 struct debug {
    369 #ifdef LOCAL
    370 ~debug() { cerr << endl; }
    371 eni(!=) cerr << boolalpha << i; ris; }
    372 eni(==) ris << range(begin(i), end(i)); }
    373 sim, class b dor(pair < b, c > d) {
    374   ris << "(" << d.first << ", " << d.second << ")";
    375 }
    376 sim dor(rge<c> d) {
    377   *this << "[";
    378   for (auto it = d.b; it != d.e; ++it)
    379     *this << ", " + 2 * (it == d.b) << *it;
    380   ris << "]";
    381 }
    382 #else
    383 sim dor(const c&) { ris; }
    384 #endif
    385 };
    386 #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
    387 
    388 const int nax = 2e5 + 5;
    389 bool forbidden[nax];
    390 
    391 int my_gcd(int a, int b) {
    392 	if(a == 0 || b == 0) return max(a, b); // return m
    393 	return __gcd(a, b);
    394 }
    395 #define __gcd use____my_gcd
    396 
    397 vector<int> which[nax];
    398 pair<int,int> dp[nax];
    399 
    400 int my_pow(int a, int b, int m) {
    401 	int r = 1;
    402 	while(b) {
    403 		if(b % 2) r = (long long) r * a % m;
    404 		a = (long long) a * a % m;
    405 		b /= 2;
    406 	}
    407 	return r;
    408 }
    409 
    410 int main() {
    411 	int n, m;
    412 	scanf("%d%d", &n, &m);
    413 	while(n--) {
    414 		int x;
    415 		scanf("%d", &x);
    416 		forbidden[x] = true;
    417 	}
    418 	#define n use_____m
    419 	for(int i = 0; i < m; ++i)
    420 		if(!forbidden[i])
    421 			which[my_gcd(i, m)].push_back(i);
    422 	if(forbidden[0])
    423 		which[m].push_back(0); // hack
    424 	for(int i = 1; i <= m; ++i)
    425 		if(!which[i].empty()) {
    426 			dp[i] = {0, 0};
    427 			for(int j = 1; j < i; ++j)
    428 				if(i % j == 0 && dp[j].first > 0)
    429 					dp[i] = max(dp[i], make_pair(dp[j].first, j));
    430 			dp[i].first += which[i].size();
    431 		}
    432 	vector<int> ans;
    433 	int x = m;
    434 	while(!which[x].empty()) {
    435 		for(int y : which[x])
    436 			ans.push_back(y);
    437 		x = dp[x].second;
    438 	}
    439 	reverse(ans.begin(), ans.end());
    440 	if(forbidden[0]) {
    441 		assert(!ans.empty());
    442 		ans.pop_back();
    443 	}
    444 	debug() << imie(ans);
    445 	int previous = 1;
    446 	printf("%d\n", (int) ans.size());
    447 	
    448 	int cnt_coprime = 0;
    449 	for(int i = 2; i < m; ++i)
    450 		if(my_gcd(i, m) == 1)
    451 			++cnt_coprime;
    452 	
    453 	for(int nxt : ans) {
    454 		if(nxt == 0) {
    455 			printf("0");
    456 			continue;
    457 		}
    458 		int a = previous / my_gcd(m, previous);
    459 		int b = nxt / my_gcd(m, nxt);
    460 		
    461 		int print = (long long) b * my_pow(a, cnt_coprime, m) % m;
    462 		print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m;
    463 		printf("%d ", print);
    464 		previous = nxt;
    465 	}
    466 	puts("");
    467 }
    468 ```
    469 
    470 **example code (java)**
    471 
    472 ```
    473 import java.io.OutputStream;
    474 import java.io.IOException;
    475 import java.io.InputStream;
    476 import java.io.OutputStream;
    477 import java.io.PrintWriter;
    478 import java.util.Arrays;
    479 import java.io.BufferedWriter;
    480 import java.io.Writer;
    481 import java.io.OutputStreamWriter;
    482 import java.util.InputMismatchException;
    483 import java.io.IOException;
    484 import java.util.ArrayList;
    485 import java.io.InputStream;
    486 
    487 /**
    488  * Built using CHelper plug-in
    489  * Actual solution is at the top
    490  */
    491 public class Main {
    492     public static void main(String[] args) {
    493         InputStream inputStream = System.in;
    494         OutputStream outputStream = System.out;
    495         InputReader in = new InputReader(inputStream);
    496         OutputWriter out = new OutputWriter(outputStream);
    497         PrefixProductSequence solver = new PrefixProductSequence();
    498         solver.solve(1, in, out);
    499         out.close();
    500     }
    501 
    502     static class PrefixProductSequence {
    503         public int[] div;
    504         public boolean[] forbidden;
    505         public ArrayList<Long> ans;
    506         public int n;
    507         public int m;
    508 
    509         public void solve(int testNumber, InputReader in, OutputWriter out) {
    510             n = in.nextInt();
    511             m = in.nextInt();
    512             forbidden = new boolean[m + 1];
    513             for (int i = 0; i < n; i++) {
    514                 forbidden[in.nextInt()] = true;
    515             }
    516             int[] add = new int[m + 1];
    517             for (int i = 0; i < m; i++) {
    518                 if (!forbidden[i]) {
    519                     int g = Utils.gcd(i, m);
    520                     add[m / g]++;
    521                 }
    522             }
    523             int[] arr = new int[m + 1];
    524             div = new int[m + 1];
    525             Arrays.fill(arr, 1);
    526             Arrays.setAll(div, x -> x);
    527             for (int i = 2; i <= m; i++) {
    528                 arr[i] += add[i];
    529                 for (int j = i + i; j <= m; j += i) {
    530                     if (arr[i] > arr[j]) {
    531                         arr[j] = arr[i];
    532                         div[j] = j / i;
    533                     }
    534                 }
    535             }
    536 
    537             ans = new ArrayList<>();
    538             solve(1, 1);
    539             out.println(ans.size());
    540             boolean first = true;
    541             for (long x : ans) {
    542                 if (!first) out.print(" ");
    543                 out.print(x);
    544                 first = false;
    545             }
    546             out.println();
    547         }
    548 
    549         public void solve(int cmult, long mm) {
    550             if (cmult == m) {
    551                 if (!forbidden[0]) {
    552                     ans.add(0L);
    553                 }
    554                 return;
    555             }
    556             int prev = 1;
    557             boolean has = false;
    558             for (int i = 1; i < m / cmult; i++) {
    559                 if (!forbidden[i * cmult] && Utils.gcd(m / cmult, i) == 1) {
    560                     long x = Utils.inv(prev, m / cmult) * i % m;
    561                     if (!has) {
    562                         has = true;
    563                         x = x * mm % m;
    564                     }
    565                     ans.add(x);
    566                     prev = i;
    567                 }
    568             }
    569             long nmm = Utils.inv(prev, m / cmult) * div[m / cmult] % m;
    570             if (!has) nmm = nmm * mm % m;
    571             solve(cmult * div[m / cmult], nmm);
    572         }
    573 
    574     }
    575 
    576     static class OutputWriter {
    577         private final PrintWriter writer;
    578 
    579         public OutputWriter(OutputStream outputStream) {
    580             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    581         }
    582 
    583         public OutputWriter(Writer writer) {
    584             this.writer = new PrintWriter(writer);
    585         }
    586 
    587         public void print(Object... objects) {
    588             for (int i = 0; i < objects.length; i++) {
    589                 if (i != 0) {
    590                     writer.print(' ');
    591                 }
    592                 writer.print(objects[i]);
    593             }
    594         }
    595 
    596         public void println() {
    597             writer.println();
    598         }
    599 
    600         public void close() {
    601             writer.close();
    602         }
    603 
    604         public void print(long i) {
    605             writer.print(i);
    606         }
    607 
    608         public void println(int i) {
    609             writer.println(i);
    610         }
    611 
    612     }
    613 
    614     static class InputReader {
    615         private InputStream stream;
    616         private byte[] buf = new byte[1024];
    617         private int curChar;
    618         private int numChars;
    619 
    620         public InputReader(InputStream stream) {
    621             this.stream = stream;
    622         }
    623 
    624         public int read() {
    625             if (this.numChars == -1) {
    626                 throw new InputMismatchException();
    627             } else {
    628                 if (this.curChar >= this.numChars) {
    629                     this.curChar = 0;
    630 
    631                     try {
    632                         this.numChars = this.stream.read(this.buf);
    633                     } catch (IOException var2) {
    634                         throw new InputMismatchException();
    635                     }
    636 
    637                     if (this.numChars <= 0) {
    638                         return -1;
    639                     }
    640                 }
    641 
    642                 return this.buf[this.curChar++];
    643             }
    644         }
    645 
    646         public int nextInt() {
    647             int c;
    648             for (c = this.read(); isSpaceChar(c); c = this.read()) {
    649                 ;
    650             }
    651 
    652             byte sgn = 1;
    653             if (c == 45) {
    654                 sgn = -1;
    655                 c = this.read();
    656             }
    657 
    658             int res = 0;
    659 
    660             while (c >= 48 && c <= 57) {
    661                 res *= 10;
    662                 res += c - 48;
    663                 c = this.read();
    664                 if (isSpaceChar(c)) {
    665                     return res * sgn;
    666                 }
    667             }
    668 
    669             throw new InputMismatchException();
    670         }
    671 
    672         public static boolean isSpaceChar(int c) {
    673             return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    674         }
    675 
    676     }
    677 
    678     static class Utils {
    679         public static long inv(long N, long M) {
    680             long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
    681             while (b != 0) {
    682                 q = a / b;
    683                 t = a % b;
    684                 a = b;
    685                 b = t;
    686                 t = x;
    687                 x = lastx - q * x;
    688                 lastx = t;
    689                 t = y;
    690                 y = lasty - q * y;
    691                 lasty = t;
    692             }
    693             return (lastx + M) % M;
    694         }
    695 
    696         public static int gcd(int a, int b) {
    697             return b == 0 ? a : gcd(b, a % b);
    698         }
    699 
    700     }
    701 }
    702 ```
    703 
    704 **Varying Kibibits**
    705 
    706 Tutorial is loading...
    707 
    708 **example code (c++, inclusion/exclusion approach)**
    709 
    710 ```
    711 // vvvvvvvvvvvvvvvvv Library code start
    712 
    713 #include <array>
    714 
    715 #define NDEBUG
    716 NDEBUG
    717 
    718 #include <algorithm>
    719 
    720 #include <cassert>
    721 #include <cstring>
    722 #include <functional>
    723 #include <iomanip>
    724 #include <iostream>
    725 #include <map>
    726 #include <set>
    727 #include <sstream>
    728 #include <string>
    729 #include <tuple>
    730 #include <unordered_map>
    731 #include <unordered_set>
    732 #include <vector>
    733 #include <memory>
    734 #include <queue>
    735 #include <random>
    736 
    737 #define forn(t, i, n) for (t i = 0; i < (n); ++i)
    738 
    739 #define rforn(t, i, n) for (t i = (n) - 1; i >= 0; --i)
    740 
    741 #define all(c) c.begin(), c.end()
    742 
    743 using namespace std;
    744 
    745 /// caide keep
    746 bool __hack = std::ios::sync_with_stdio(false);
    747 /// caide keep
    748 auto __hack1 = cin.tie(nullptr);
    749 
    750 // Section with adoption of array and vector algorithms.
    751 
    752 // 32 bit ints (sum LSB + MSB == 32)
    753 
    754 // TODO: Section with some container algorithms
    755 
    756 #define ENABLE_IF(e) typename enable_if<e>::type* = nullptr
    757 
    758 namespace template_util {
    759     template<class T>
    760     constexpr T min(T a, T b) {
    761         return a < b ? a : b;
    762     }
    763 
    764     
    765     constexpr int bytecount(uint64_t x) {
    766         return x ? 1 + bytecount(x >> 8) : 0;
    767     }
    768 
    769     /// caide keep
    770     template<int N>
    771     struct bytetype {
    772         typedef uint64_t type;
    773     };
    774 
    775     /// caide keep
    776     template<>
    777     struct bytetype<4> {
    778         typedef uint32_t type;
    779     };
    780 
    781     /// caide keep
    782     template<>
    783     struct bytetype<3> {
    784         
    785     };
    786 
    787     /// caide keep
    788     template<>
    789     struct bytetype<2> {
    790         
    791     };
    792 
    793     /// caide keep
    794     template<>
    795     struct bytetype<1> {
    796         typedef uint8_t type;
    797     };
    798 
    799     /// caide keep
    800     template<>
    801     struct bytetype<0> {
    802         typedef uint8_t type;
    803     };
    804 
    805     /// caide keep
    806     template<uint64_t N>
    807     struct minimal_uint : bytetype<bytecount(N)> {
    808     };
    809 }
    810 
    811 template<class T>
    812 T next(istream& in) {
    813     T ret;
    814     in >> ret;
    815     return ret;
    816 }
    817 
    818 template<class T>
    819 vector<T> next_vector(istream& in, size_t n) {
    820     vector<T> ret(n);
    821     for (size_t i = 0; i < n; ++i) {
    822         ret[i] = next<T>(in);
    823     }
    824     return ret;
    825 }
    826 
    827 #define dbg(...) ;
    828 
    829 /*
    830 TODOs:
    831  cache invs
    832  primitive root
    833  discrete log
    834 
    835  tests!!!
    836 */
    837 
    838 namespace mod_impl {
    839     /// caide keep
    840     template <class T>
    841     constexpr inline T mod(T MOD) {
    842         return MOD;
    843     }
    844 
    845     /// caide keep
    846     template <class T>
    847     constexpr inline T mod(T* MOD) {
    848         return *MOD;
    849     }
    850 
    851     /// caide keep
    852     template <class T>
    853     constexpr inline T max_mod(T MOD) {
    854         return MOD - 1;
    855     }
    856 
    857     /// caide keep
    858     template <class T>
    859     constexpr inline T max_mod(T*) {
    860         return numeric_limits<T>::max() - 1;
    861     }
    862 
    863     
    864     constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) {
    865         return a > ~b ? 0 : a + b;
    866     }
    867 
    868     constexpr inline uint64_t combine_max_mul(uint64_t a, uint64_t b) {
    869         return a > numeric_limits<uint64_t>::max() / b ? 0 : a * b;
    870     }
    871 
    872     /// caide keep
    873     template <class T>
    874     constexpr inline uint64_t next_divisible(T mod, uint64_t max) {
    875         return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod);
    876     }
    877 
    878     /// caide keep
    879     template <class T>
    880     constexpr inline uint64_t next_divisible(T*, uint64_t) {
    881         return 0;
    882     }
    883 
    884     //caide keep
    885     constexpr int IF_THRESHOLD = 2;
    886 
    887     template <class T, T MOD_VALUE, uint64_t MAX,
    888             class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
    889             ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    890     inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
    891         return value;
    892     }
    893 
    894     template <class T, T MOD_VALUE, uint64_t MAX,
    895             class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
    896             ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    897     inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
    898         while (value >= mod(MOD_VALUE)) {
    899             value -= mod(MOD_VALUE);
    900         }
    901         return (RET)value;
    902     }
    903 
    904     template <class T, T MOD_VALUE, uint64_t MAX,
    905              class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
    906              ENABLE_IF(IF_THRESHOLD * max_mod(MOD_VALUE) < MAX || is_pointer<T>::value)>
    907     inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
    908         return (RET)(value % mod(MOD_VALUE));
    909     }
    910 }
    911 
    912 #define MOD mod_impl::mod(MOD_VALUE)
    913 #define MAX_MOD mod_impl::max_mod(MOD_VALUE)
    914 
    915 struct DenormTag {};
    916 
    917 template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)>
    918 struct ModVal {
    919     typedef typename template_util::minimal_uint<MAX>::type storage;
    920     storage value;
    921 
    922     /// caide keep
    923     inline ModVal(): value(0) {
    924         assert(MOD >= 2);
    925     }
    926 
    927     
    928     inline ModVal(storage v, DenormTag): value(v) {
    929         assert(MOD >= 2);
    930         assert(v <= MAX);
    931     };
    932 
    933     inline operator ModVal<T, MOD_VALUE>() {
    934         return {v(), DenormTag()};
    935     };
    936 
    937     explicit inline operator uint64_t() const {
    938         return v();
    939     }
    940 
    941     typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const {
    942         return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value);
    943     }
    944 };
    945 
    946 template <class T, T MOD_VALUE, uint64_t MAX,
    947         uint64_t NEW_MAX = mod_impl::next_divisible(MOD_VALUE, MAX),
    948         ENABLE_IF(NEW_MAX != 0),
    949         class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
    950 inline Ret operator-(const ModVal<T, MOD_VALUE, MAX>& o) {
    951     static_assert(NEW_MAX <= numeric_limits<typename Ret::storage>::max(), "bad unary minus template");
    952     assert(NEW_MAX % MOD == 0 && o.value <= NEW_MAX);
    953     return {typename Ret::storage(NEW_MAX - o.value), DenormTag()};
    954 }
    955 
    956 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
    957         uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2),
    958         ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
    959 inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    960     return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()};
    961 }
    962 
    963 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
    964         uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
    965         ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
    966 inline Ret operator*(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    967     return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.value), DenormTag()};
    968 }
    969 
    970 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
    971         uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
    972         uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
    973         ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX1 <= MAX2),
    974         class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX1, MAX_MOD)>>
    975 inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    976     return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.v()), DenormTag()};
    977 }
    978 
    979 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
    980         uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
    981         uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
    982         ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX2 < MAX1),
    983         class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX2)>>
    984 inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    985     return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.value), DenormTag()};
    986 }
    987 
    988 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
    989 inline auto operator-(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) -> decltype(lhs + (-rhs)) {
    990     return lhs + (-rhs);
    991 }
    992 
    993 template <class T, T MOD_VALUE, uint64_t MAX>
    994 inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
    995     lhs = lhs + rhs;
    996     return lhs;
    997 }
    998 
    999 template <class T, T MOD_VALUE, uint64_t MAX>
   1000 inline ModVal<T, MOD_VALUE>& operator-=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
   1001     lhs = lhs - rhs;
   1002     return lhs;
   1003 }
   1004 
   1005 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
   1006 inline bool operator!=(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) {
   1007     return lhs.v() != rhs.v();
   1008 }
   1009 
   1010 template <class T, T MOD_VALUE, class MOD_TYPE>
   1011 struct ModCompanion {
   1012     typedef MOD_TYPE mod_type;
   1013     typedef ModVal<mod_type, MOD_VALUE> type;
   1014     
   1015 
   1016     template <uint64_t C>
   1017     inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() {
   1018         return {C, DenormTag()};
   1019     };
   1020 
   1021     template <uint64_t MAX = numeric_limits<uint64_t>::max()>
   1022     inline static ModVal<mod_type, MOD_VALUE, MAX> wrap(uint64_t x) {
   1023         assert(x <= MAX);
   1024         return {typename ModVal<mod_type, MOD_VALUE, MAX>::storage(x), DenormTag()};
   1025     };
   1026 
   1027     template <uint64_t MAX, ENABLE_IF(!is_pointer<T>::value && MAX <= MAX_MOD)>
   1028     inline static ModVal<mod_type, MOD_VALUE> inv(const ModVal<mod_type, MOD_VALUE, MAX>& x) {
   1029         if (x.value == 1) {
   1030             return c<1>();
   1031         }
   1032         return -(wrap<MAX_MOD / 2>(MOD / x.value) * inv(wrap<MAX>(MOD % x.value)));
   1033     };
   1034 
   1035     
   1036 };
   1037 
   1038 #undef MOD
   1039 #undef MAX_MOD
   1040 
   1041 template <uint64_t MOD_VALUE>
   1042 struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> {
   1043     template<uint64_t VAL>
   1044     static constexpr uint64_t literal_builder() {
   1045         return VAL;
   1046     }
   1047 
   1048     template<uint64_t VAL, char DIGIT, char... REST>
   1049     static constexpr uint64_t literal_builder() {
   1050         return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>();
   1051     }
   1052 };
   1053 
   1054 #define REGISTER_MOD_LITERAL(mod, suffix) \
   1055 template <char... DIGITS> mod::type operator "" _##suffix() { \
   1056     return mod::c<mod::literal_builder<0, DIGITS...>()>(); \
   1057 }
   1058 
   1059 // ^^^^^^^^^^^^^^^^^ Library code end
   1060 
   1061 using md = Mod<1000000007>;
   1062 using mt = md::type;
   1063 REGISTER_MOD_LITERAL(md, mod)
   1064 
   1065 using Val = tuple<int, mt, mt>;
   1066 
   1067 mt pow2s[1000001], powInv2s[1000001];
   1068 
   1069 mt pow2(int p) {
   1070     return p < 0 ? powInv2s[-p] : pow2s[p];
   1071 }
   1072 
   1073 Val mul(Val a, Val b) {
   1074     const mt p2a = pow2(get<0>(a));
   1075     const mt p2b = pow2(get<0>(b));
   1076     return Val{get<0>(a) + get<0>(b), p2a * get<1>(b) + get<1>(a) * p2b, p2a * get<2>(b) + 2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b};
   1077 }
   1078 
   1079 Val inv(Val a) {
   1080     Val b;
   1081     get<0>(b) = -get<0>(a);
   1082     const mt p2b = pow2(get<0>(b));
   1083     get<1>(b) = -p2b * (get<1>(a) * p2b);
   1084     get<2>(b) = -p2b * (2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b);
   1085     return b;
   1086 }
   1087 
   1088 Val d[1000000][7];
   1089 mt dSum[1000000][7];
   1090 
   1091 void solve(istream& in, ostream& out) {
   1092     pow2s[0] = powInv2s[0] = 1_mod;
   1093     mt inv2 = md::inv(2_mod);
   1094     forn (int, i, 1000000) {
   1095         pow2s[i + 1] = pow2s[i] * 2_mod;
   1096         powInv2s[i + 1] = powInv2s[i] * inv2;
   1097     }
   1098 
   1099     int n = next<int>(in);
   1100     auto as = next_vector<int>(in, n);
   1101     sort(all(as));
   1102     uint64_t ans = 0;
   1103     int add[1 << 6];
   1104     forn (int, mask, 1 << 6) {
   1105         add[mask] = 0;
   1106         int mask1 = mask;
   1107         forn (int, it, 6) {
   1108             add[mask] = add[mask] * 10 + (mask1 & 1);
   1109             mask1 /= 2;
   1110         }
   1111     }
   1112     int asIt = n - 1;
   1113     rforn (int, x, 1000000) {
   1114         int badMask = 0;
   1115         int x1 = x;
   1116         forn (int, it, 6) {
   1117             badMask = 2 * badMask + (x1 % 10 == 9 ? 1 : 0);
   1118             x1 /= 10;
   1119         }
   1120         d[x][0] = Val{0, 0_mod, 0_mod};
   1121         dSum[x][0] = 0_mod;
   1122         forn (int, bit, 6) {
   1123             d[x][bit + 1] = d[x][bit];
   1124             dSum[x][bit + 1] = dSum[x][bit];
   1125             if (!(badMask & (1 << bit))) {
   1126                 d[x][bit + 1] = mul(d[x][bit + 1], inv(d[x + add[1 << bit]][bit]));
   1127                 dSum[x][bit + 1] -=  dSum[x + add[1 << bit]][bit];
   1128             }
   1129         }
   1130         auto val = inv(d[x][6]);
   1131         while (asIt >= 0 && as[asIt] == x) {
   1132             --asIt;
   1133             val = mul(val, Val{1, md::wrap(x), md::wrap(1ULL * x * x)});
   1134         }
   1135         auto sum = get<2>(val) + dSum[x][6];
   1136         forn (int, bit, 6) {
   1137             d[x][bit] = mul(d[x][bit], val);
   1138             dSum[x][bit] += get<2>(val);
   1139         }
   1140         if (sum != 0_mod) {
   1141             dbg(x, sum, x * uint64_t(sum));
   1142             ans ^= x * uint64_t(sum);
   1143         }
   1144     }
   1145     out << ans << endl;
   1146 }
   1147 
   1148 int main() {
   1149     solve(cin, cout);
   1150     return 0;
   1151 }
   1152 ```
   1153 
   1154 **example code (java, FWHT approach)**
   1155 
   1156 ```
   1157 import java.io.OutputStream;
   1158 import java.io.IOException;
   1159 import java.io.InputStream;
   1160 import java.io.OutputStream;
   1161 import java.io.PrintWriter;
   1162 import java.io.BufferedWriter;
   1163 import java.io.Writer;
   1164 import java.io.OutputStreamWriter;
   1165 import java.util.InputMismatchException;
   1166 import java.io.IOException;
   1167 import java.io.InputStream;
   1168 
   1169 /**
   1170  * Built using CHelper plug-in
   1171  * Actual solution is at the top
   1172  */
   1173 public class Main {
   1174     public static void main(String[] args) {
   1175         InputStream inputStream = System.in;
   1176         OutputStream outputStream = System.out;
   1177         InputReader in = new InputReader(inputStream);
   1178         OutputWriter out = new OutputWriter(outputStream);
   1179         MinAddition solver = new MinAddition();
   1180         solver.solve(1, in, out);
   1181         out.close();
   1182     }
   1183 
   1184     static class MinAddition {
   1185         public int[] pow10 = {1, 10, 100, 1000, 10000, 100000, 1000000};
   1186         public int MAXN = 1000000;
   1187         public int LOG = 6;
   1188         public int mod = 1000000007;
   1189 
   1190         public void solve(int testNumber, InputReader in, OutputWriter out) {
   1191             int n = in.nextInt();
   1192             int[] freq = new int[MAXN];
   1193             int[] sum = new int[MAXN];
   1194             int[] sum2 = new int[MAXN];
   1195             int[] pow2 = new int[n + 1];
   1196             pow2[0] = 1;
   1197             for (int i = 1; i <= n; i++) pow2[i] = (pow2[i - 1] << 1) % mod;
   1198             for (int i = 0; i < n; i++) {
   1199                 int a = in.nextInt();
   1200                 freq[a]++;
   1201                 sum[a] += a;
   1202                 if (sum[a] >= mod) sum[a] -= mod;
   1203                 int x = (int) (1L * a * a % mod);
   1204                 sum2[a] += x;
   1205                 if (sum2[a] >= mod) sum2[a] -= mod;
   1206             }
   1207 
   1208             int[] mod10 = new int[MAXN];
   1209             for (int i = 0; i < 10; i++) mod10[i] = i;
   1210             for (int i = 10; i < MAXN; i++) mod10[i] = mod10[i - 10];
   1211 
   1212             for (int level = LOG - 1; level >= 0; level--) {
   1213                 for (int i = MAXN - 1; i >= 0; i--) {
   1214                     int d = mod10[i / pow10[level]];
   1215                     if (d > 0) {
   1216                         int p = i - pow10[level];
   1217                         freq[p] += freq[i];
   1218                         sum[p] += sum[i];
   1219                         if (sum[p] >= mod) sum[p] -= mod;
   1220                         sum2[p] += sum2[i];
   1221                         if (sum2[p] >= mod) sum2[p] -= mod;
   1222                     }
   1223                 }
   1224             }
   1225             for (int i = 0; i < MAXN; i++) {
   1226                 int sdiff = (int) ((1L * sum[i] * sum[i] + mod - sum2[i]) % mod);
   1227                 int ssame = sum2[i];
   1228                 int g = 0;
   1229                 if (freq[i] >= 1)
   1230                     g += (int) (1L * ssame * pow2[freq[i] - 1] % mod);
   1231                 if (freq[i] >= 2)
   1232                     g += (int) (1L * sdiff * pow2[freq[i] - 2] % mod);
   1233                 while (g >= mod) g -= mod;
   1234                 freq[i] = g;
   1235             }
   1236 
   1237             for (int level = 0; level < LOG; level++) {
   1238                 for (int i = 0; i < MAXN; i++) {
   1239                     int d = mod10[i / pow10[level]];
   1240                     if (d + 1 < 10) {
   1241                         int p = i + pow10[level];
   1242                         freq[i] -= freq[p];
   1243                         if (freq[i] < 0) freq[i] += mod;
   1244                     }
   1245                 }
   1246             }
   1247 
   1248             long s = 0;
   1249             for (int i = 0; i < MAXN; i++) {
   1250                 s ^= 1L * i * freq[i];
   1251             }
   1252             out.println(s);
   1253         }
   1254 
   1255     }
   1256 
   1257     static class OutputWriter {
   1258         private final PrintWriter writer;
   1259 
   1260         public OutputWriter(OutputStream outputStream) {
   1261             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
   1262         }
   1263 
   1264         public OutputWriter(Writer writer) {
   1265             this.writer = new PrintWriter(writer);
   1266         }
   1267 
   1268         public void close() {
   1269             writer.close();
   1270         }
   1271 
   1272         public void println(long i) {
   1273             writer.println(i);
   1274         }
   1275 
   1276     }
   1277 
   1278     static class InputReader {
   1279         private InputStream stream;
   1280         private byte[] buf = new byte[1024];
   1281         private int curChar;
   1282         private int numChars;
   1283 
   1284         public InputReader(InputStream stream) {
   1285             this.stream = stream;
   1286         }
   1287 
   1288         public int read() {
   1289             if (this.numChars == -1) {
   1290                 throw new InputMismatchException();
   1291             } else {
   1292                 if (this.curChar >= this.numChars) {
   1293                     this.curChar = 0;
   1294 
   1295                     try {
   1296                         this.numChars = this.stream.read(this.buf);
   1297                     } catch (IOException var2) {
   1298                         throw new InputMismatchException();
   1299                     }
   1300 
   1301                     if (this.numChars <= 0) {
   1302                         return -1;
   1303                     }
   1304                 }
   1305 
   1306                 return this.buf[this.curChar++];
   1307             }
   1308         }
   1309 
   1310         public int nextInt() {
   1311             int c;
   1312             for (c = this.read(); isSpaceChar(c); c = this.read()) {
   1313                 ;
   1314             }
   1315 
   1316             byte sgn = 1;
   1317             if (c == 45) {
   1318                 sgn = -1;
   1319                 c = this.read();
   1320             }
   1321 
   1322             int res = 0;
   1323 
   1324             while (c >= 48 && c <= 57) {
   1325                 res *= 10;
   1326                 res += c - 48;
   1327                 c = this.read();
   1328                 if (isSpaceChar(c)) {
   1329                     return res * sgn;
   1330                 }
   1331             }
   1332 
   1333             throw new InputMismatchException();
   1334         }
   1335 
   1336         public static boolean isSpaceChar(int c) {
   1337             return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
   1338         }
   1339 
   1340     }
   1341 }
   1342 ```
   1343 
   1344 **Verifying Kingdom**
   1345 
   1346 Tutorial is loading...
   1347 
   1348 **example code (c++)**
   1349 
   1350 ```
   1351 // vvvvvvvvvvvvvvvvv Library code start
   1352 
   1353 #define NDEBUG
   1354 NDEBUG
   1355 
   1356 #include <algorithm>
   1357 #include <array>
   1358 #include <cassert>
   1359 #include <cstring>
   1360 #include <functional>
   1361 #include <iomanip>
   1362 #include <iostream>
   1363 #include <map>
   1364 #include <set>
   1365 #include <sstream>
   1366 #include <string>
   1367 #include <tuple>
   1368 #include <unordered_map>
   1369 #include <unordered_set>
   1370 #include <vector>
   1371 #include <memory>
   1372 #include <queue>
   1373 #include <random>
   1374 
   1375 #define forn(t, i, n) for (t i = 0; i < (n); ++i)
   1376 #define foran(t, i, a, n) for (t i = (a); i < (n); ++i)
   1377 
   1378 using namespace std;
   1379 
   1380 /// caide keep
   1381 bool __hack = std::ios::sync_with_stdio(false);
   1382 /// caide keep
   1383 auto __hack1 = cin.tie(nullptr);
   1384 
   1385 template<class T>
   1386 inline T mn(T arg) {
   1387     return arg;
   1388 }
   1389 
   1390 template<class T, class... Args>
   1391 inline bool rmx(T &to, Args... args) {
   1392     auto v = mn(args...);
   1393     if (to < v) {
   1394         to = v;
   1395         return true;
   1396     }
   1397     return false;
   1398 }
   1399 
   1400 // Section with adoption of array and vector algorithms.
   1401 
   1402 // 32 bit ints (sum LSB + MSB == 32)
   1403 
   1404 // TODO: Section with some container algorithms
   1405 
   1406 namespace template_util {
   1407     
   1408 
   1409     constexpr int bytecount(uint64_t x) {
   1410         return x ? 1 + bytecount(x >> 8) : 0;
   1411     }
   1412 
   1413     /// caide keep
   1414     template<int N>
   1415     struct bytetype {
   1416         
   1417     };
   1418 
   1419     /// caide keep
   1420     template<>
   1421     struct bytetype<4> {
   1422         
   1423     };
   1424 
   1425     /// caide keep
   1426     template<>
   1427     struct bytetype<3> {
   1428         
   1429     };
   1430 
   1431     /// caide keep
   1432     template<>
   1433     struct bytetype<2> {
   1434         
   1435     };
   1436 
   1437     /// caide keep
   1438     template<>
   1439     struct bytetype<1> {
   1440         
   1441     };
   1442 
   1443     /// caide keep
   1444     template<>
   1445     struct bytetype<0> {
   1446         
   1447     };
   1448 
   1449     /// caide keep
   1450     template<uint64_t N>
   1451     struct minimal_uint : bytetype<bytecount(N)> {
   1452     };
   1453 }
   1454 
   1455 template<class T>
   1456 T next(istream& in) {
   1457     T ret;
   1458     in >> ret;
   1459     return ret;
   1460 }
   1461 
   1462 // ^^^^^^^^^^^^^^^^^ Library code end
   1463 
   1464 int tr[1000][3];
   1465 int l[1000], r[1000];
   1466 bool col[1000];
   1467 int ans[2000];
   1468 
   1469 tuple<int, int, int> chooseDfs(int total, int i, int p = -1) {
   1470     int size = 1, best = -1, bestSize = 1000000000, maxSize = 0;
   1471     forn (int, e, 3) {
   1472         int j = tr[i][e];
   1473         if (j != p && j >= 0 && !col[j]) {
   1474             auto r1 = chooseDfs(total, j, i);
   1475             if (get<1>(r1) < bestSize) {
   1476                 best = get<0>(r1);
   1477                 bestSize = get<1>(r1);
   1478             }
   1479             size += get<2>(r1);
   1480             rmx(maxSize, get<2>(r1));
   1481         }
   1482     }
   1483     rmx(maxSize, total - size);
   1484     if (maxSize < bestSize) {
   1485         best = i;
   1486         bestSize = maxSize;
   1487     }
   1488     return tuple<int, int, int>{best, bestSize, size};
   1489 }
   1490 
   1491 int sizeDfs(int i, int p = -1) {
   1492     auto r = 1;
   1493     forn (int, e, 3) {
   1494         int j = tr[i][e];
   1495         if (j != p && j >= 0 && !col[j]) {
   1496             r += sizeDfs(j, i);
   1497         }
   1498     }
   1499     return r;
   1500 }
   1501 
   1502 void ansDfs(int n, int i) {
   1503     forn (int, e, 2) {
   1504         if (tr[i][e] >= 0) {
   1505             ansDfs(n, tr[i][e]);
   1506         }
   1507         ans[tr[i][e] < 0 ? -2 - tr[i][e] : n + tr[i][e]] = n + i + 1;
   1508     }
   1509 }
   1510 
   1511 void solve(istream& in, ostream& out) {
   1512     auto q = [&](int a, int b, int c) {
   1513         out << a + 1 << " " << b + 1 << " " << c + 1 << endl;
   1514         string s = next<string>(in);
   1515         if (s == "X") {
   1516             return 2;
   1517         } else if (s == "Y") {
   1518             return 1;
   1519         } else if (s == "Z") {
   1520             return 0;
   1521         } else {
   1522             throw 42;
   1523         }
   1524     };
   1525     int n = next<int>(in);
   1526     memset(tr, -1, sizeof(tr));
   1527     tr[0][0] = -2;
   1528     tr[0][1] = -3;
   1529     l[0] = 0;
   1530     r[0] = 1;
   1531     foran (int, i, 2, n) {
   1532         memset(col, 0, sizeof(col));
   1533         int x = 0;
   1534         while (true) {
   1535             x = get<0>(chooseDfs(sizeDfs(x), x));
   1536             int e = q(l[x], r[x], i);
   1537             if (tr[x][e] < 0 || col[tr[x][e]]) {
   1538                 if (tr[x][e] >= 0) {
   1539                     forn (int, e1, 3) {
   1540                         if (tr[tr[x][e]][e1] == x) {
   1541                             tr[tr[x][e]][e1] = i - 1;
   1542                         }
   1543                     }
   1544                 }
   1545                 tr[i - 1][e] = tr[x][e];
   1546                 tr[x][e] = i - 1;
   1547                 tr[i - 1][e == 0 ? 1 : 0] = -2 - i;
   1548                 tr[i - 1][e == 2 ? 1 : 2] = x;
   1549                 l[i - 1] = tr[i - 1][0] < 0 ? -2 - tr[i - 1][0] : l[tr[i - 1][0]];
   1550                 r[i - 1] = tr[i - 1][1] < 0 ? -2 - tr[i - 1][1] : r[tr[i - 1][1]];
   1551                 break;
   1552             }
   1553             col[x] = true;
   1554             x = tr[x][e];
   1555         }
   1556     }
   1557     int r = 0;
   1558     while (tr[r][2] != -1) {
   1559         r = tr[r][2];
   1560     }
   1561     ans[n + r] = -1;
   1562     ansDfs(n, r);
   1563     out << "-1\n";
   1564     forn (int, i, 2 * n - 1) {
   1565         out << ans[i] << " ";
   1566     }
   1567     out << "\n";
   1568 }
   1569 
   1570 int main() {
   1571     solve(cin, cout);
   1572     return 0;
   1573 }
   1574 ```
   1575 
   1576 **example code (java)**
   1577 
   1578 ```
   1579 import java.io.OutputStream;
   1580 import java.io.IOException;
   1581 import java.io.InputStream;
   1582 import java.io.OutputStream;
   1583 import java.io.PrintWriter;
   1584 import java.io.BufferedWriter;
   1585 import java.io.Writer;
   1586 import java.io.OutputStreamWriter;
   1587 import java.util.InputMismatchException;
   1588 import java.io.IOException;
   1589 import java.io.InputStream;
   1590 
   1591 /**
   1592  * Built using CHelper plug-in
   1593  * Actual solution is at the top
   1594  */
   1595 public class Main {
   1596     public static void main(String[] args) {
   1597         InputStream inputStream = System.in;
   1598         OutputStream outputStream = System.out;
   1599         InputReader in = new InputReader(inputStream);
   1600         OutputWriter out = new OutputWriter(outputStream);
   1601         ForgottenTree solver = new ForgottenTree();
   1602         solver.solve(1, in, out);
   1603         out.close();
   1604     }
   1605 
   1606     static class ForgottenTree {
   1607         public InputReader in;
   1608         public OutputWriter out;
   1609         public int nidx;
   1610         public int n;
   1611         public int[] par;
   1612 
   1613         public void solve(int testNumber, InputReader in, OutputWriter out) {
   1614             this.in = in;
   1615             this.out = out;
   1616 
   1617             n = in.nextInt();
   1618             nidx = n;
   1619             ForgottenTree.Node root = new ForgottenTree.Node(0);
   1620             ForgottenTree.Node.cgen = 0;
   1621             for (int i = 1; i < n; i++) {
   1622                 ForgottenTree.Node.cgen++;
   1623                 root.getLeaves();
   1624                 root = insert(root, i);
   1625             }
   1626             out.println(-1);
   1627             par = new int[2 * n - 1];
   1628             dfs(root, -2);
   1629             out.println(par);
   1630         }
   1631 
   1632         public String ask(int a, int b, int c) {
   1633             out.println((a + 1) + " " + (b + 1) + " " + (c + 1));
   1634             out.flush();
   1635             String ret = in.next();
   1636             if (ret.equals("-1")) System.exit(0);
   1637             return ret;
   1638         }
   1639 
   1640         public void dfs(ForgottenTree.Node root, int p) {
   1641             par[root.label] = p + 1;
   1642             if (root.lchild != null) {
   1643                 dfs(root.lchild, root.label);
   1644                 dfs(root.rchild, root.label);
   1645             }
   1646         }
   1647 
   1648         public ForgottenTree.Node insert(ForgottenTree.Node root, int label) {
   1649             if (!root.active()) {
   1650                 return add(root, label);
   1651             }
   1652             root.dfs();
   1653 
   1654             if (root.lchild == null) {
   1655                 return add(root, label);
   1656             }
   1657 
   1658             int curleaves = root.nleaves;
   1659             if (curleaves <= 1) {
   1660                 int nnodes = 0;
   1661                 ForgottenTree.Node cur = root;
   1662                 while (!cur.isLeaf()) {
   1663                     nnodes++;
   1664                     if (cur.lchild.active()) cur = cur.lchild;
   1665                     else cur = cur.rchild;
   1666                 }
   1667                 cur = root;
   1668                 int depth = 0;
   1669                 while (2 * (depth + 1) < nnodes) {
   1670                     if (cur.lchild.active()) cur = cur.lchild;
   1671                     else cur = cur.rchild;
   1672                     depth++;
   1673                 }
   1674 
   1675                 return process(root, cur, label);
   1676             }
   1677 
   1678             ForgottenTree.Node cur = root;
   1679             while (true) {
   1680                 if (cur.lchild == null) {
   1681                     if (cur.par == null) {
   1682                         return add(cur, label);
   1683                     }
   1684                     if (cur.which == 0) {
   1685                         cur.par.setChild(0, add(cur, label));
   1686                         return root;
   1687                     } else {
   1688                         cur.par.setChild(1, add(cur, label));
   1689                         return root;
   1690                     }
   1691                 }
   1692                 int x1 = cur.lchild.active() ? cur.lchild.nleaves : 0;
   1693                 int x2 = cur.rchild.active() ? cur.rchild.nleaves : 0;
   1694 
   1695                 if (x1 * 2 > curleaves) {
   1696                     cur = cur.lchild;
   1697                     continue;
   1698                 }
   1699                 if (x2 * 2 > curleaves) {
   1700                     cur = cur.rchild;
   1701                     continue;
   1702                 }
   1703 
   1704                 return process(root, cur, label);
   1705             }
   1706         }
   1707 
   1708         public ForgottenTree.Node process(ForgottenTree.Node root, ForgottenTree.Node cur, int label) {
   1709             String s = ask(cur.x, cur.y, label);
   1710             switch (s) {
   1711                 case "X":
   1712                     if (cur.par == null) {
   1713                         return add(cur, label);
   1714                     }
   1715                     cur.disable();
   1716                     return insert(root, label);
   1717                 case "Y":
   1718                     cur.setChild(1, insert(cur.rchild, label));
   1719                     return root;
   1720                 case "Z":
   1721                     cur.setChild(0, insert(cur.lchild, label));
   1722                     return root;
   1723                 default:
   1724                     throw new RuntimeException();
   1725             }
   1726         }
   1727 
   1728         public ForgottenTree.Node add(ForgottenTree.Node cnode, int label) {
   1729             ForgottenTree.Node add = new ForgottenTree.Node(nidx++);
   1730             add.setChild(0, cnode);
   1731             add.setChild(1, new ForgottenTree.Node(label));
   1732             return add;
   1733         }
   1734 
   1735         static class Node {
   1736             public static int cgen;
   1737             public int x;
   1738             public int y;
   1739             public int label;
   1740             public int gen;
   1741             public int nleaves;
   1742             public int which;
   1743             public ForgottenTree.Node lchild;
   1744             public ForgottenTree.Node rchild;
   1745             public ForgottenTree.Node par;
   1746 
   1747             public Node(int label) {
   1748                 this.lchild = null;
   1749                 this.rchild = null;
   1750                 this.par = null;
   1751                 this.which = 0;
   1752                 this.label = label;
   1753                 this.gen = 0;
   1754                 this.nleaves = 1;
   1755             }
   1756 
   1757             public boolean active() {
   1758                 return gen < cgen;
   1759             }
   1760 
   1761             public void disable() {
   1762                 this.gen = cgen;
   1763             }
   1764 
   1765             public boolean isLeaf() {
   1766                 return lchild == null || (!lchild.active() && !rchild.active());
   1767             }
   1768 
   1769             public void setChild(int which, ForgottenTree.Node x) {
   1770                 if (which == 0) {
   1771                     this.lchild = x;
   1772                 } else {
   1773                     this.rchild = x;
   1774                 }
   1775                 x.par = this;
   1776                 x.which = which;
   1777             }
   1778 
   1779             public void dfs() {
   1780                 if (isLeaf()) {
   1781                     this.nleaves = 1;
   1782                     return;
   1783                 }
   1784 
   1785                 this.nleaves = 0;
   1786                 if (lchild.active()) {
   1787                     lchild.dfs();
   1788                     this.nleaves += lchild.nleaves;
   1789                 }
   1790                 if (rchild.active()) {
   1791                     rchild.dfs();
   1792                     this.nleaves += rchild.nleaves;
   1793                 }
   1794             }
   1795 
   1796             public void getLeaves() {
   1797                 if (lchild == null) {
   1798                     this.x = this.y = label;
   1799                     return;
   1800                 }
   1801                 lchild.getLeaves();
   1802                 rchild.getLeaves();
   1803                 this.x = lchild.x;
   1804                 this.y = rchild.x;
   1805             }
   1806 
   1807         }
   1808 
   1809     }
   1810 
   1811     static class InputReader {
   1812         private InputStream stream;
   1813         private byte[] buf = new byte[1024];
   1814         private int curChar;
   1815         private int numChars;
   1816 
   1817         public InputReader(InputStream stream) {
   1818             this.stream = stream;
   1819         }
   1820 
   1821         public int read() {
   1822             if (this.numChars == -1) {
   1823                 throw new InputMismatchException();
   1824             } else {
   1825                 if (this.curChar >= this.numChars) {
   1826                     this.curChar = 0;
   1827 
   1828                     try {
   1829                         this.numChars = this.stream.read(this.buf);
   1830                     } catch (IOException var2) {
   1831                         throw new InputMismatchException();
   1832                     }
   1833 
   1834                     if (this.numChars <= 0) {
   1835                         return -1;
   1836                     }
   1837                 }
   1838 
   1839                 return this.buf[this.curChar++];
   1840             }
   1841         }
   1842 
   1843         public int nextInt() {
   1844             int c;
   1845             for (c = this.read(); isSpaceChar(c); c = this.read()) {
   1846                 ;
   1847             }
   1848 
   1849             byte sgn = 1;
   1850             if (c == 45) {
   1851                 sgn = -1;
   1852                 c = this.read();
   1853             }
   1854 
   1855             int res = 0;
   1856 
   1857             while (c >= 48 && c <= 57) {
   1858                 res *= 10;
   1859                 res += c - 48;
   1860                 c = this.read();
   1861                 if (isSpaceChar(c)) {
   1862                     return res * sgn;
   1863                 }
   1864             }
   1865 
   1866             throw new InputMismatchException();
   1867         }
   1868 
   1869         public String next() {
   1870             int c;
   1871             while (isSpaceChar(c = this.read())) {
   1872                 ;
   1873             }
   1874 
   1875             StringBuilder result = new StringBuilder();
   1876             result.appendCodePoint(c);
   1877 
   1878             while (!isSpaceChar(c = this.read())) {
   1879                 result.appendCodePoint(c);
   1880             }
   1881 
   1882             return result.toString();
   1883         }
   1884 
   1885         public static boolean isSpaceChar(int c) {
   1886             return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
   1887         }
   1888 
   1889     }
   1890 
   1891     static class OutputWriter {
   1892         private final PrintWriter writer;
   1893 
   1894         public OutputWriter(OutputStream outputStream) {
   1895             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
   1896         }
   1897 
   1898         public OutputWriter(Writer writer) {
   1899             this.writer = new PrintWriter(writer);
   1900         }
   1901 
   1902         public void print(Object... objects) {
   1903             for (int i = 0; i < objects.length; i++) {
   1904                 if (i != 0) {
   1905                     writer.print(' ');
   1906                 }
   1907                 writer.print(objects[i]);
   1908             }
   1909         }
   1910 
   1911         public void print(int[] array) {
   1912             for (int i = 0; i < array.length; i++) {
   1913                 if (i != 0) {
   1914                     writer.print(' ');
   1915                 }
   1916                 writer.print(array[i]);
   1917             }
   1918         }
   1919 
   1920         public void println(int[] array) {
   1921             print(array);
   1922             writer.println();
   1923         }
   1924 
   1925         public void println(Object... objects) {
   1926             print(objects);
   1927             writer.println();
   1928         }
   1929 
   1930         public void close() {
   1931             writer.close();
   1932         }
   1933 
   1934         public void flush() {
   1935             writer.flush();
   1936         }
   1937 
   1938         public void println(int i) {
   1939             writer.println(i);
   1940         }
   1941 
   1942     }
   1943 }
   1944 ```