{"id":71,"date":"2011-03-24T07:49:22","date_gmt":"2011-03-23T23:49:22","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=71"},"modified":"2013-10-15T00:35:47","modified_gmt":"2013-10-14T16:35:47","slug":"sdoi-2009-hh%e7%9a%84%e9%a1%b9%e9%93%be","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/sdoi-2009-hh%e7%9a%84%e9%a1%b9%e9%93%be\/","title":{"rendered":"[SDOI 2009] HH\u7684\u9879\u94fe"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u7ed9\u5b9a\u6570\u5217{Ai}\uff0c\u79bb\u7ebf\u8be2\u95ee\u533a\u95f4\u76f8\u5f02\u6570\u5b57\u7684\u6570\u76ee\u3002\u6570\u5217\u957f\u5ea6 n\uff0c\u8be2\u95ee m \u6b21\u3002<br \/>\n\uff08n <= 50000, m <= 200000, Ai <= 1000000 ...\uff09\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<style>.gist table { margin-bottom: 0; }<\/style>\n<div style=\"tab-size: 8\" id=\"gist6978412\" class=\"gist\">\n<div class=\"gist-file\" translate=\"no\" data-color-mode=\"light\" data-light-theme=\"light\">\n<div class=\"gist-data\">\n<div class=\"js-gist-file-update-container js-task-list-container\">\n<div id=\"file-bzoj_1878-cpp\" class=\"file my-2\">\n<div itemprop=\"text\"\n      class=\"Box-body p-0 blob-wrapper data type-c  \"\n      style=\"overflow: auto\" tabindex=\"0\" role=\"region\"\n      aria-label=\"BZOJ_1878.cpp content, created by lychees on 04:35PM on October 14, 2013.\"\n    ><\/p>\n<div class=\"js-check-hidden-unicode js-blob-code-container blob-code-content\">\n<p>  <template class=\"js-file-alert-template\"><\/p>\n<div data-view-component=\"true\" class=\"flash flash-warn flash-full d-flex flex-items-center\">\n  <svg aria-hidden=\"true\" height=\"16\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" data-view-component=\"true\" class=\"octicon octicon-alert\">\n    <path d=\"M6.457 1.047c.659-1.234 2.427-1.234 3.086 0l6.082 11.378A1.75 1.75 0 0 1 14.082 15H1.918a1.75 1.75 0 0 1-1.543-2.575Zm1.763.707a.25.25 0 0 0-.44 0L1.698 13.132a.25.25 0 0 0 .22.368h12.164a.25.25 0 0 0 .22-.368Zm.53 3.996v2.5a.75.75 0 0 1-1.5 0v-2.5a.75.75 0 0 1 1.5 0ZM9 11a1 1 0 1 1-2 0 1 1 0 0 1 2 0Z\"><\/path>\n<\/svg><br \/>\n    <span><br \/>\n      This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.<br \/>\n      <a class=\"Link--inTextBlock\" href=\"https:\/\/github.co\/hiddenchars\" target=\"_blank\">Learn more about bidirectional Unicode characters<\/a><br \/>\n    <\/span><\/p>\n<div data-view-component=\"true\" class=\"flash-action\">        <a href=\"{{ revealButtonHref }}\" data-view-component=\"true\" class=\"btn-sm btn\">    Show hidden characters<br \/>\n<\/a>\n<\/div>\n<\/div>\n<p><\/template><br \/>\n<template class=\"js-line-alert-template\"><br \/>\n  <span aria-label=\"This line has hidden Unicode characters\" data-view-component=\"true\" class=\"line-alert tooltipped tooltipped-e\"><br \/>\n    <svg aria-hidden=\"true\" height=\"16\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" data-view-component=\"true\" class=\"octicon octicon-alert\">\n    <path d=\"M6.457 1.047c.659-1.234 2.427-1.234 3.086 0l6.082 11.378A1.75 1.75 0 0 1 14.082 15H1.918a1.75 1.75 0 0 1-1.543-2.575Zm1.763.707a.25.25 0 0 0-.44 0L1.698 13.132a.25.25 0 0 0 .22.368h12.164a.25.25 0 0 0 .22-.368Zm.53 3.996v2.5a.75.75 0 0 1-1.5 0v-2.5a.75.75 0 0 1 1.5 0ZM9 11a1 1 0 1 1-2 0 1 1 0 0 1 2 0Z\"><\/path>\n<\/svg><br \/>\n<\/span><\/template><\/p>\n<table data-hpc class=\"highlight tab-size js-file-line-container\" data-tab-size=\"4\" data-paste-markdown-skip data-tagsearch-path=\"BZOJ_1878.cpp\">\n<tr>\n<td id=\"file-bzoj_1878-cpp-L1\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"1\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC1\" class=\"blob-code blob-code-inner js-file-line\">\/** Micro Mezz Macro Flation &#8212; Overheated Economy ., Last Update: Sep. 22th 2013 **\/ \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L2\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"2\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC2\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L3\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"3\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC3\" class=\"blob-code blob-code-inner js-file-line\">\/** Header .. **\/ \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L4\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"4\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC4\" class=\"blob-code blob-code-inner js-file-line\">#pragma comment(linker, &quot;\/STACK:36777216&quot;)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L5\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"5\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC5\" class=\"blob-code blob-code-inner js-file-line\">\/\/#pragma GCC optimize (&quot;O2&quot;)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L6\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"6\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC6\" class=\"blob-code blob-code-inner js-file-line\">#define LOCAL<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L7\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"7\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC7\" class=\"blob-code blob-code-inner js-file-line\">\/\/#include &quot;testlib.h&quot;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L8\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"8\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC8\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;functional&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L9\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"9\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC9\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;algorithm&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L10\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"10\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC10\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;iostream&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L11\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"11\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC11\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;fstream&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L12\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"12\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC12\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;sstream&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L13\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"13\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC13\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;iomanip&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L14\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"14\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC14\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;numeric&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L15\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"15\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC15\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;cstring&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L16\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"16\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC16\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;climits&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L17\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"17\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC17\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;cassert&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L18\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"18\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC18\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;complex&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L19\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"19\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC19\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;cstdio&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L20\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"20\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC20\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;string&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L21\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"21\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC21\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;vector&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L22\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"22\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC22\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;bitset&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L23\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"23\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC23\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;queue&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L24\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"24\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC24\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;stack&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L25\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"25\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC25\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;cmath&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L26\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"26\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC26\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;ctime&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L27\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"27\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC27\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;list&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L28\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"28\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC28\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;set&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L29\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"29\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC29\" class=\"blob-code blob-code-inner js-file-line\">#include &lt;map&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L30\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"30\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC30\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L31\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"31\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC31\" class=\"blob-code blob-code-inner js-file-line\">\/\/#include &lt;tr1\/unordered_set&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L32\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"32\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC32\" class=\"blob-code blob-code-inner js-file-line\">\/\/#include &lt;tr1\/unordered_map&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L33\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"33\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC33\" class=\"blob-code blob-code-inner js-file-line\">\/\/#include &lt;array&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L34\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"34\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC34\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L35\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"35\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC35\" class=\"blob-code blob-code-inner js-file-line\">using namespace std;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L36\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"36\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC36\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L37\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"37\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC37\" class=\"blob-code blob-code-inner js-file-line\">#define REP(i, n) for (int i=0;i&lt;int(n);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L38\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"38\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC38\" class=\"blob-code blob-code-inner js-file-line\">#define FOR(i, a, b) for (int i=int(a);i&lt;int(b);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L39\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"39\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC39\" class=\"blob-code blob-code-inner js-file-line\">#define DWN(i, b, a) for (int i=int(b-1);i&gt;=int(a);&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L40\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"40\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC40\" class=\"blob-code blob-code-inner js-file-line\">#define REP_1(i, n) for (int i=1;i&lt;=int(n);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L41\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"41\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC41\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_1(i, a, b) for (int i=int(a);i&lt;=int(b);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L42\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"42\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC42\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_1(i, b, a) for (int i=int(b);i&gt;=int(a);&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L43\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"43\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC43\" class=\"blob-code blob-code-inner js-file-line\">#define REP_C(i, n) for (int n____=int(n),i=0;i&lt;n____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L44\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"44\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC44\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_C(i, a, b) for (int b____=int(b),i=a;i&lt;b____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L45\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"45\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC45\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i&gt;=a____;&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L46\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"46\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC46\" class=\"blob-code blob-code-inner js-file-line\">#define REP_N(i, n) for (i=0;i&lt;int(n);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L47\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"47\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC47\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_N(i, a, b) for (i=int(a);i&lt;int(b);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L48\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"48\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC48\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_N(i, b, a) for (i=int(b-1);i&gt;=int(a);&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L49\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"49\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC49\" class=\"blob-code blob-code-inner js-file-line\">#define REP_1_C(i, n) for (int n____=int(n),i=1;i&lt;=n____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L50\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"50\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC50\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i&lt;=b____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L51\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"51\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC51\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i&gt;=a____;&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L52\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"52\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC52\" class=\"blob-code blob-code-inner js-file-line\">#define REP_1_N(i, n) for (i=1;i&lt;=int(n);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L53\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"53\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC53\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_1_N(i, a, b) for (i=int(a);i&lt;=int(b);++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L54\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"54\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC54\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_1_N(i, b, a) for (i=int(b);i&gt;=int(a);&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L55\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"55\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC55\" class=\"blob-code blob-code-inner js-file-line\">#define REP_C_N(i, n) for (int n____=(i=0,int(n));i&lt;n____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L56\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"56\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC56\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i&lt;b____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L57\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"57\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC57\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i&gt;=a____;&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L58\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"58\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC58\" class=\"blob-code blob-code-inner js-file-line\">#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i&lt;=n____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L59\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"59\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC59\" class=\"blob-code blob-code-inner js-file-line\">#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i&lt;=b____;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L60\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"60\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC60\" class=\"blob-code blob-code-inner js-file-line\">#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i&gt;=a____;&#8211;i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L61\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"61\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC61\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L62\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"62\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC62\" class=\"blob-code blob-code-inner js-file-line\">#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L63\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"63\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC63\" class=\"blob-code blob-code-inner js-file-line\">#define REP_S(i, str) for (char*i=str;*i;++i)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L64\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"64\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC64\" class=\"blob-code blob-code-inner js-file-line\">#define REP_L(i, hd, nxt) for (int i=hd;i;i=nxt[i])<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L65\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"65\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC65\" class=\"blob-code blob-code-inner js-file-line\">#define REP_G(i, u) REP_L(i,hd[u],suc)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L66\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"66\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC66\" class=\"blob-code blob-code-inner js-file-line\">#define REP_SS(x, s) for (int x=s;x;x=(x-1)&amp;s)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L67\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"67\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC67\" class=\"blob-code blob-code-inner js-file-line\">#define DO(n) for ( int ____n = n; ____n&#8211;&gt;0; )<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L68\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"68\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC68\" class=\"blob-code blob-code-inner js-file-line\">#define REP_2(i, j, n, m) REP(i, n) REP(j, m)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L69\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"69\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC69\" class=\"blob-code blob-code-inner js-file-line\">#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L70\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"70\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC70\" class=\"blob-code blob-code-inner js-file-line\">#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L71\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"71\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC71\" class=\"blob-code blob-code-inner js-file-line\">#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L72\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"72\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC72\" class=\"blob-code blob-code-inner js-file-line\">#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L73\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"73\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC73\" class=\"blob-code blob-code-inner js-file-line\">#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L74\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"74\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC74\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L75\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"75\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC75\" class=\"blob-code blob-code-inner js-file-line\">#define ALL(A) A.begin(), A.end()<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L76\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"76\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC76\" class=\"blob-code blob-code-inner js-file-line\">#define LLA(A) A.rbegin(), A.rend()<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L77\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"77\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC77\" class=\"blob-code blob-code-inner js-file-line\">#define CPY(A, B) memcpy(A, B, sizeof(A))<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L78\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"78\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC78\" class=\"blob-code blob-code-inner js-file-line\">#define INS(A, P, B) A.insert(A.begin() + P, B)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L79\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"79\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC79\" class=\"blob-code blob-code-inner js-file-line\">#define ERS(A, P) A.erase(A.begin() + P)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L80\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"80\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC80\" class=\"blob-code blob-code-inner js-file-line\">#define BSC(A, x) (lower_bound(ALL(A), x) &#8211; A.begin())<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L81\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"81\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC81\" class=\"blob-code blob-code-inner js-file-line\">#define CTN(T, x) (T.find(x) != T.end())<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L82\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"82\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC82\" class=\"blob-code blob-code-inner js-file-line\">#define SZ(A) int((A).size())<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L83\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"83\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC83\" class=\"blob-code blob-code-inner js-file-line\">#define PB push_back<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L84\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"84\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC84\" class=\"blob-code blob-code-inner js-file-line\">#define MP(A, B) make_pair(A, B)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L85\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"85\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC85\" class=\"blob-code blob-code-inner js-file-line\">#define PTT pair&lt;T, T&gt;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L86\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"86\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC86\" class=\"blob-code blob-code-inner js-file-line\">#define Ts *this<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L87\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"87\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC87\" class=\"blob-code blob-code-inner js-file-line\">#define rTs return Ts<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L88\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"88\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC88\" class=\"blob-code blob-code-inner js-file-line\">#define fi first<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L89\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"89\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC89\" class=\"blob-code blob-code-inner js-file-line\">#define se second<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L90\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"90\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC90\" class=\"blob-code blob-code-inner js-file-line\">#define re real()<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L91\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"91\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC91\" class=\"blob-code blob-code-inner js-file-line\">#define im imag()<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L92\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"92\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC92\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L93\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"93\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC93\" class=\"blob-code blob-code-inner js-file-line\">#define Rush for(int ____T=RD(); ____T&#8211;;)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L94\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"94\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC94\" class=\"blob-code blob-code-inner js-file-line\">#define Display(A, n, m) {                      \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L95\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"95\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC95\" class=\"blob-code blob-code-inner js-file-line\">  REP(i, n){\t\t                            \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L96\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"96\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC96\" class=\"blob-code blob-code-inner js-file-line\">        REP(j, m-1) cout &lt;&lt; A[i][j] &lt;&lt; &quot; &quot;;     \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L97\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"97\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC97\" class=\"blob-code blob-code-inner js-file-line\">        cout &lt;&lt; A[i][m-1] &lt;&lt; endl;\t\t        \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L98\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"98\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC98\" class=\"blob-code blob-code-inner js-file-line\">\t}\t\t\t\t\t\t                    \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L99\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"99\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC99\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L100\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"100\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC100\" class=\"blob-code blob-code-inner js-file-line\">#define Display_1(A, n, m) {                    \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L101\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"101\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC101\" class=\"blob-code blob-code-inner js-file-line\">\tREP_1(i, n){\t\t                        \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L102\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"102\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC102\" class=\"blob-code blob-code-inner js-file-line\">        REP_1(j, m-1) cout &lt;&lt; A[i][j] &lt;&lt; &quot; &quot;;   \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L103\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"103\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC103\" class=\"blob-code blob-code-inner js-file-line\">        cout &lt;&lt; A[i][m] &lt;&lt; endl;\t\t        \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L104\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"104\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC104\" class=\"blob-code blob-code-inner js-file-line\">\t}\t\t\t\t\t\t                    \\<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L105\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"105\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC105\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L106\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"106\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC106\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L107\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"107\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC107\" class=\"blob-code blob-code-inner js-file-line\">typedef long long LL;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L108\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"108\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC108\" class=\"blob-code blob-code-inner js-file-line\">\/\/typedef long double DB;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L109\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"109\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC109\" class=\"blob-code blob-code-inner js-file-line\">typedef double DB;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L110\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"110\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC110\" class=\"blob-code blob-code-inner js-file-line\">typedef unsigned uint;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L111\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"111\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC111\" class=\"blob-code blob-code-inner js-file-line\">typedef unsigned long long uLL;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L112\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"112\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC112\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L113\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"113\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC113\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;int&gt; VI;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L114\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"114\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC114\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;char&gt; VC;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L115\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"115\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC115\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;string&gt; VS;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L116\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"116\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC116\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;LL&gt; VL;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L117\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"117\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC117\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;DB&gt; VF;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L118\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"118\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC118\" class=\"blob-code blob-code-inner js-file-line\">typedef set&lt;int&gt; SI;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L119\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"119\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC119\" class=\"blob-code blob-code-inner js-file-line\">typedef set&lt;string&gt; SS;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L120\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"120\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC120\" class=\"blob-code blob-code-inner js-file-line\">typedef map&lt;int, int&gt; MII;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L121\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"121\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC121\" class=\"blob-code blob-code-inner js-file-line\">typedef map&lt;string, int&gt; MSI;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L122\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"122\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC122\" class=\"blob-code blob-code-inner js-file-line\">typedef pair&lt;int, int&gt; PII;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L123\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"123\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC123\" class=\"blob-code blob-code-inner js-file-line\">typedef pair&lt;LL, LL&gt; PLL;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L124\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"124\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC124\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;PII&gt; VII;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L125\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"125\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC125\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;VI&gt; VVI;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L126\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"126\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC126\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;VII&gt; VVII;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L127\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"127\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC127\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L128\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"128\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC128\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; RD(T &amp;);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L129\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"129\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC129\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void OT(const T &amp;);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L130\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"130\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC130\" class=\"blob-code blob-code-inner js-file-line\">\/\/inline int RD(){int x; return RD(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L131\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"131\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC131\" class=\"blob-code blob-code-inner js-file-line\">inline LL RD(){LL x; return RD(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L132\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"132\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC132\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L133\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"133\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC133\" class=\"blob-code blob-code-inner js-file-line\">inline DB RF(){DB x; return RF(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L134\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"134\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC134\" class=\"blob-code blob-code-inner js-file-line\">inline char* RS(char *s);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L135\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"135\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC135\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;c);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L136\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"136\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC136\" class=\"blob-code blob-code-inner js-file-line\">inline char RC();<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L137\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"137\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC137\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;c){scanf(&quot; %c&quot;, &amp;c); return c;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L138\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"138\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC138\" class=\"blob-code blob-code-inner js-file-line\">inline char RC(){char c; return RC(c);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L139\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"139\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC139\" class=\"blob-code blob-code-inner js-file-line\">\/\/inline char&amp; RC(char &amp;c){c = getchar(); return c;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L140\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"140\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC140\" class=\"blob-code blob-code-inner js-file-line\">\/\/inline char RC(){return getchar();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L141\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"141\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC141\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L142\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"142\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC142\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; RDD(T &amp;);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L143\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"143\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC143\" class=\"blob-code blob-code-inner js-file-line\">inline LL RDD(){LL x; return RDD(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L144\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"144\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC144\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L145\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"145\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC145\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1){RD(x0), RD(x1); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L146\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"146\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC146\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2){RD(x0), RD(x1), RD(x2); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L147\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"147\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC147\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L148\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"148\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC148\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L149\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"149\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC149\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L150\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"150\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC150\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5, T6 &amp;x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L151\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"151\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC151\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1){OT(x0), OT(x1);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L152\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"152\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC152\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2){OT(x0), OT(x1), OT(x2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L153\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"153\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC153\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3){OT(x0), OT(x1), OT(x2), OT(x3);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L154\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"154\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC154\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L155\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"155\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC155\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4, const T5 &amp;x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L156\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"156\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC156\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4, const T5 &amp;x5, const T6 &amp;x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L157\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"157\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC157\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b){RC(a), RC(b); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L158\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"158\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC158\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b, char &amp;c){RC(a), RC(b), RC(c); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L159\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"159\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC159\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d){RC(a), RC(b), RC(c), RC(d); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L160\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"160\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC160\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L161\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"161\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC161\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e, char &amp;f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L162\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"162\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC162\" class=\"blob-code blob-code-inner js-file-line\">inline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e, char &amp;f, char &amp;g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L163\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"163\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC163\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b){RF(a), RF(b); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L164\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"164\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC164\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c){RF(a), RF(b), RF(c); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L165\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"165\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC165\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d){RF(a), RF(b), RF(c), RF(d); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L166\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"166\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC166\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L167\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"167\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC167\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e, DB &amp;f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L168\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"168\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC168\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e, DB &amp;f, DB &amp;g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L169\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"169\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC169\" class=\"blob-code blob-code-inner js-file-line\">inline void RS(char *s1, char *s2){RS(s1), RS(s2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L170\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"170\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC170\" class=\"blob-code blob-code-inner js-file-line\">inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L171\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"171\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC171\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0,class T1&gt;inline void RDD(T0&amp;a, T1&amp;b){RDD(a),RDD(b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L172\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"172\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC172\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0,class T1,class T2&gt;inline void RDD(T0&amp;a, T1&amp;b, T2&amp;c){RDD(a),RDD(b),RDD(c);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L173\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"173\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC173\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L174\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"174\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC174\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void RST(T &amp;A){memset(A, 0, sizeof(A));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L175\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"175\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC175\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void FLC(T &amp;A, int x){memset(A, x, sizeof(A));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L176\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"176\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC176\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void CLR(T &amp;A){A.clear();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L177\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"177\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC177\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L178\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"178\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC178\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1&gt; inline void RST(T0 &amp;A0, T1 &amp;A1){RST(A0), RST(A1);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L179\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"179\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC179\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){RST(A0), RST(A1), RST(A2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L180\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"180\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC180\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){RST(A0), RST(A1), RST(A2), RST(A3);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L181\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"181\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC181\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L182\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"182\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC182\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L183\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"183\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC183\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L184\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"184\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC184\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, int x){FLC(A0, x), FLC(A1, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L185\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"185\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC185\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L186\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"186\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC186\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L187\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"187\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC187\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L188\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"188\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC188\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L189\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"189\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC189\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L190\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"190\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC190\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void CLR(priority_queue&lt;T, vector&lt;T&gt;, less&lt;T&gt; &gt; &amp;Q){while (!Q.empty()) Q.pop();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L191\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"191\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC191\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void CLR(priority_queue&lt;T, vector&lt;T&gt;, greater&lt;T&gt; &gt; &amp;Q){while (!Q.empty()) Q.pop();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L192\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"192\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC192\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void CLR(stack&lt;T&gt; &amp;S){while (!S.empty()) S.pop();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L193\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"193\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC193\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L194\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"194\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC194\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1){CLR(A0), CLR(A1);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L195\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"195\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC195\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){CLR(A0), CLR(A1), CLR(A2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L196\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"196\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC196\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L197\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"197\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC197\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L198\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"198\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC198\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L199\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"199\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC199\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L200\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"200\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC200\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline void CLR(T &amp;A, int n){REP(i, n) CLR(A[i]);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L201\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"201\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC201\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L202\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"202\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC202\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline bool EPT(T &amp;a){return a.empty();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L203\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"203\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC203\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; SRT(T &amp;A){sort(ALL(A)); return A;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L204\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"204\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC204\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T, class C&gt; inline T&amp; SRT(T &amp;A, C B){sort(ALL(A), B); return A;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L205\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"205\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC205\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; RVS(T &amp;A){reverse(ALL(A)); return A;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L206\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"206\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC206\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; UNQQ(T &amp;A){A.resize(unique(ALL(A))-A.begin());return A;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L207\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"207\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC207\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; UNQ(T &amp;A){SRT(A);return UNQQ(A);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L208\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"208\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC208\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L209\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"209\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC209\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L210\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"210\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC210\" class=\"blob-code blob-code-inner js-file-line\">\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L211\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"211\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC211\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L212\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"212\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC212\" class=\"blob-code blob-code-inner js-file-line\">\/** Constant List .. **\/ \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L213\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"213\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC213\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L214\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"214\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC214\" class=\"blob-code blob-code-inner js-file-line\">const int MOD = int(1e9) + 7;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L215\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"215\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC215\" class=\"blob-code blob-code-inner js-file-line\">\/\/int MOD = 99990001;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L216\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"216\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC216\" class=\"blob-code blob-code-inner js-file-line\">const int INF = 0x3f3f3f3f;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L217\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"217\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC217\" class=\"blob-code blob-code-inner js-file-line\">const LL INFF = 0x3f3f3f3f3f3f3f3fLL;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L218\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"218\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC218\" class=\"blob-code blob-code-inner js-file-line\">const DB EPS = 1e-9;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L219\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"219\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC219\" class=\"blob-code blob-code-inner js-file-line\">const DB OO = 1e20;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L220\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"220\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC220\" class=\"blob-code blob-code-inner js-file-line\">const DB PI = acos(-1.0); \/\/M_PI;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L221\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"221\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC221\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L222\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"222\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC222\" class=\"blob-code blob-code-inner js-file-line\">const int dx[] = {-1, 0, 1, 0};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L223\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"223\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC223\" class=\"blob-code blob-code-inner js-file-line\">const int dy[] = {0, 1, 0, -1};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L224\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"224\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC224\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L225\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"225\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC225\" class=\"blob-code blob-code-inner js-file-line\">\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L226\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"226\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC226\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L227\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"227\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC227\" class=\"blob-code blob-code-inner js-file-line\">\/** Add On .. **\/ \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L228\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"228\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC228\" class=\"blob-code blob-code-inner js-file-line\">\/\/ &lt;&lt;= &#39;0. Nichi Joo ., \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L229\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"229\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC229\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L230\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"230\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC230\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; checkMin(T &amp;a,const T b){if (b&lt;a) a=b;return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L231\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"231\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC231\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; checkMax(T &amp;a,const T b){if (a&lt;b) a=b;return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L232\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"232\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC232\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; checkMin(T &amp;a, T &amp;b, const T x){checkMin(a, x), checkMin(b, x);return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L233\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"233\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC233\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; checkMax(T &amp;a, T &amp;b, const T x){checkMax(a, x), checkMax(b, x);return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L234\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"234\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC234\" class=\"blob-code blob-code-inner js-file-line\">template &lt;class T, class C&gt; inline T&amp; checkMin(T&amp; a, const T b, C c){if (c(b,a)) a = b;return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L235\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"235\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC235\" class=\"blob-code blob-code-inner js-file-line\">template &lt;class T, class C&gt; inline T&amp; checkMax(T&amp; a, const T b, C c){if (c(a,b)) a = b;return a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L236\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"236\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC236\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T min(T a, T b, T c){return min(min(a, b), c);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L237\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"237\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC237\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T max(T a, T b, T c){return max(max(a, b), c);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L238\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"238\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC238\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L239\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"239\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC239\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L240\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"240\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC240\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T sqr(T a){return a*a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L241\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"241\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC241\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T cub(T a){return a*a*a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L242\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"242\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC242\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T ceil(T x, T y){return (x &#8211; 1) \/ y + 1;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L243\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"243\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC243\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; T abs(T x){return x&gt;0?x:-x;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L244\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"244\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC244\" class=\"blob-code blob-code-inner js-file-line\">inline int sgn(DB x){return x &lt; -EPS ? -1 : x &gt; EPS;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L245\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"245\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC245\" class=\"blob-code blob-code-inner js-file-line\">inline int sgn(DB x, DB y){return sgn(x &#8211; y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L246\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"246\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC246\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L247\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"247\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC247\" class=\"blob-code blob-code-inner js-file-line\">inline DB cos(DB a, DB b, DB c){return (sqr(a)+sqr(b)-sqr(c))\/(2*a*b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L248\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"248\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC248\" class=\"blob-code blob-code-inner js-file-line\">inline DB cot(DB x){return 1.\/tan(x);};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L249\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"249\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC249\" class=\"blob-code blob-code-inner js-file-line\">inline DB sec(DB x){return 1.\/cos(x);};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L250\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"250\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC250\" class=\"blob-code blob-code-inner js-file-line\">inline DB csc(DB x){return 1.\/sin(x);};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L251\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"251\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC251\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L252\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"252\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC252\" class=\"blob-code blob-code-inner js-file-line\">\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L253\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"253\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC253\" class=\"blob-code blob-code-inner js-file-line\">\/\/ &lt;&lt;= &#39;1. Bitwise Operation ., \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L254\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"254\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC254\" class=\"blob-code blob-code-inner js-file-line\">namespace BO{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L255\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"255\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC255\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L256\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"256\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC256\" class=\"blob-code blob-code-inner js-file-line\">inline bool _1(int x, int i){return bool(x&amp;1&lt;&lt;i);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L257\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"257\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC257\" class=\"blob-code blob-code-inner js-file-line\">inline bool _1(LL x, int i){return bool(x&amp;1LL&lt;&lt;i);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L258\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"258\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC258\" class=\"blob-code blob-code-inner js-file-line\">inline LL _1(int i){return 1LL&lt;&lt;i;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L259\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"259\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC259\" class=\"blob-code blob-code-inner js-file-line\">inline LL _U(int i){return _1(i) &#8211; 1;};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L260\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"260\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC260\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L261\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"261\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC261\" class=\"blob-code blob-code-inner js-file-line\">inline int reverse_bits(int x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L262\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"262\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC262\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 1) &amp; 0x55555555) | ((x &lt;&lt; 1) &amp; 0xaaaaaaaa);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L263\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"263\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC263\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 2) &amp; 0x33333333) | ((x &lt;&lt; 2) &amp; 0xcccccccc);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L264\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"264\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC264\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 4) &amp; 0x0f0f0f0f) | ((x &lt;&lt; 4) &amp; 0xf0f0f0f0);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L265\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"265\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC265\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 8) &amp; 0x00ff00ff) | ((x &lt;&lt; 8) &amp; 0xff00ff00);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L266\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"266\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC266\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt;16) &amp; 0x0000ffff) | ((x &lt;&lt;16) &amp; 0xffff0000);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L267\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"267\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC267\" class=\"blob-code blob-code-inner js-file-line\">    return x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L268\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"268\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC268\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L269\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"269\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC269\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L270\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"270\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC270\" class=\"blob-code blob-code-inner js-file-line\">inline LL reverse_bits(LL x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L271\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"271\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC271\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 1) &amp; 0x5555555555555555LL) | ((x &lt;&lt; 1) &amp; 0xaaaaaaaaaaaaaaaaLL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L272\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"272\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC272\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 2) &amp; 0x3333333333333333LL) | ((x &lt;&lt; 2) &amp; 0xccccccccccccccccLL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L273\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"273\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC273\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 4) &amp; 0x0f0f0f0f0f0f0f0fLL) | ((x &lt;&lt; 4) &amp; 0xf0f0f0f0f0f0f0f0LL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L274\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"274\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC274\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt; 8) &amp; 0x00ff00ff00ff00ffLL) | ((x &lt;&lt; 8) &amp; 0xff00ff00ff00ff00LL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L275\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"275\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC275\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt;16) &amp; 0x0000ffff0000ffffLL) | ((x &lt;&lt;16) &amp; 0xffff0000ffff0000LL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L276\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"276\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC276\" class=\"blob-code blob-code-inner js-file-line\">    x = ((x &gt;&gt;32) &amp; 0x00000000ffffffffLL) | ((x &lt;&lt;32) &amp; 0xffffffff00000000LL);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L277\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"277\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC277\" class=\"blob-code blob-code-inner js-file-line\">    return x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L278\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"278\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC278\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L279\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"279\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC279\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L280\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"280\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC280\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline bool odd(T x){return x&amp;1;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L281\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"281\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC281\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline bool even(T x){return !odd(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L282\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"282\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC282\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T low_bit(T x) {return x &amp; -x;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L283\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"283\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC283\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L284\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"284\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC284\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T cover_bit(T x){T p = 1; while (p &lt; x) p &lt;&lt;= 1;return p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L285\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"285\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC285\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline int cover_idx(T x){int p = 0; while (_1(p) &lt; x ) ++p; return p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L286\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"286\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC286\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L287\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"287\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC287\" class=\"blob-code blob-code-inner js-file-line\">inline int clz(int x){return __builtin_clz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L288\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"288\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC288\" class=\"blob-code blob-code-inner js-file-line\">inline int clz(LL x){return __builtin_clzll(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L289\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"289\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC289\" class=\"blob-code blob-code-inner js-file-line\">inline int ctz(int x){return __builtin_ctz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L290\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"290\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC290\" class=\"blob-code blob-code-inner js-file-line\">inline int ctz(LL x){return __builtin_ctzll(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L291\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"291\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC291\" class=\"blob-code blob-code-inner js-file-line\">inline int lg2(int x){return !x ? -1 : 31 &#8211; clz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L292\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"292\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC292\" class=\"blob-code blob-code-inner js-file-line\">inline int lg2(LL x){return !x ? -1 : 63 &#8211; clz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L293\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"293\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC293\" class=\"blob-code blob-code-inner js-file-line\">inline int low_idx(int x){return !x ? -1 : ctz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L294\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"294\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC294\" class=\"blob-code blob-code-inner js-file-line\">inline int low_idx(LL x){return !x ? -1 : ctz(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L295\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"295\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC295\" class=\"blob-code blob-code-inner js-file-line\">inline int high_idx(int x){return lg2(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L296\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"296\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC296\" class=\"blob-code blob-code-inner js-file-line\">inline int high_idx(LL x){return lg2(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L297\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"297\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC297\" class=\"blob-code blob-code-inner js-file-line\">inline int parity(int x){return __builtin_parity(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L298\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"298\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC298\" class=\"blob-code blob-code-inner js-file-line\">inline int parity(LL x){return __builtin_parityll(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L299\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"299\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC299\" class=\"blob-code blob-code-inner js-file-line\">inline int count_bits(int x){return __builtin_popcount(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L300\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"300\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC300\" class=\"blob-code blob-code-inner js-file-line\">inline int count_bits(LL x){return __builtin_popcountll(x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L301\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"301\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC301\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L302\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"302\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC302\" class=\"blob-code blob-code-inner js-file-line\">} using namespace BO;\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L303\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"303\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC303\" class=\"blob-code blob-code-inner js-file-line\">\/\/ &lt;&lt;= &#39;9. Comutational Geometry .,\/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L304\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"304\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC304\" class=\"blob-code blob-code-inner js-file-line\">namespace CG{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L305\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"305\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC305\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L306\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"306\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC306\" class=\"blob-code blob-code-inner js-file-line\">#define cPo const Po&amp;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L307\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"307\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC307\" class=\"blob-code blob-code-inner js-file-line\">#define cLine const Line&amp;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L308\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"308\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC308\" class=\"blob-code blob-code-inner js-file-line\">#define cSeg const Seg&amp;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L309\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"309\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC309\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L310\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"310\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC310\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(DB x,DB y){return sqr(x)+sqr(y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L311\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"311\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC311\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L312\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"312\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC312\" class=\"blob-code blob-code-inner js-file-line\">struct Po{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L313\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"313\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC313\" class=\"blob-code blob-code-inner js-file-line\">    DB x,y;Po(DB x=0,DB y=0):x(x),y(y){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L314\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"314\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC314\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L315\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"315\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC315\" class=\"blob-code blob-code-inner js-file-line\">    void in(){RF(x,y);}void out(){printf(&quot;(%.2f,%.2f)&quot;,x,y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L316\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"316\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC316\" class=\"blob-code blob-code-inner js-file-line\">    inline friend istream&amp;operator&gt;&gt;(istream&amp;i,Po&amp;p){return i&gt;&gt;p.x&gt;&gt;p.y;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L317\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"317\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC317\" class=\"blob-code blob-code-inner js-file-line\">    inline friend ostream&amp;operator&lt;&lt;(ostream&amp;o,Po p){return o&lt;&lt;&quot;(&quot;&lt;&lt;p.x&lt;&lt;&quot;, &quot;&lt;&lt;p.y&lt;&lt; &quot;)&quot;;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L318\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"318\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC318\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L319\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"319\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC319\" class=\"blob-code blob-code-inner js-file-line\">    Po operator-()const{return Po(-x,-y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L320\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"320\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC320\" class=\"blob-code blob-code-inner js-file-line\">    Po&amp;operator+=(cPo p){x+=p.x,y+=p.y;rTs;}Po&amp;operator-=(cPo p){x-=p.x,y-=p.y;rTs;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L321\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"321\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC321\" class=\"blob-code blob-code-inner js-file-line\">    Po&amp;operator*=(DB k){x*=k,y*=k;rTs;}Po&amp;operator\/=(DB k){x\/=k,y\/=k;rTs;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L322\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"322\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC322\" class=\"blob-code blob-code-inner js-file-line\">    Po&amp;operator*=(cPo p){rTs=Ts*p;}Po&amp;operator\/=(cPo p){rTs=Ts\/p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L323\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"323\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC323\" class=\"blob-code blob-code-inner js-file-line\">    Po operator+(cPo p)const{return Po(x+p.x,y+p.y);}Po operator-(cPo p)const{return Po(x-p.x,y-p.y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L324\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"324\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC324\" class=\"blob-code blob-code-inner js-file-line\">    Po operator*(DB k)const{return Po(x*k,y*k);}Po operator\/(DB k)const{return Po(x\/k,y\/k);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L325\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"325\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC325\" class=\"blob-code blob-code-inner js-file-line\">    Po operator*(cPo p)const{return Po(x*p.x-y*p.y,y*p.x+x*p.y);}Po operator\/(cPo p)const{return Po(x*p.x+y*p.y,y*p.x-x*p.y)\/p.len2();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L326\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"326\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC326\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L327\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"327\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC327\" class=\"blob-code blob-code-inner js-file-line\">    bool operator==(cPo p)const{return!sgn(x,p.x)&amp;&amp;!sgn(y,p.y);};bool operator!=(cPo p)const{return sgn(x,p.x)||sgn(y,p.y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L328\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"328\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC328\" class=\"blob-code blob-code-inner js-file-line\">    bool operator&lt;(cPo p)const{return sgn(x,p.x)&lt;0||!sgn(x,p.x)&amp;&amp;sgn(y,p.y)&lt;0;}bool operator&lt;=(cPo p)const{return sgn(x,p.x)&lt;0||!sgn(x,p.x)&amp;&amp;sgn(y,p.y)&lt;=0;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L329\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"329\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC329\" class=\"blob-code blob-code-inner js-file-line\">    bool operator&gt;(cPo p)const{return!(Ts&lt;=p);}bool operator &gt;=(cPo p)const{return!(Ts&lt;p);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L330\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"330\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC330\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L331\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"331\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC331\" class=\"blob-code blob-code-inner js-file-line\">    DB len2()const{return dist2(x,y);}DB len()const{return sqrt(len2());}DB arg()const{return atan2(y,x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L332\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"332\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC332\" class=\"blob-code blob-code-inner js-file-line\">    Po&amp;_1(){rTs\/=len();}Po&amp;conj(){y=-y;rTs;}Po&amp;lt(){swap(x,y),x=-x;rTs;}Po&amp;rt(){swap(x,y),y=-y;rTs;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L333\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"333\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC333\" class=\"blob-code blob-code-inner js-file-line\">    Po&amp;rot(DB a,cPo o=Po()){Ts-=o;Ts*=Po(cos(a),sin(a));rTs+=o;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L334\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"334\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC334\" class=\"blob-code blob-code-inner js-file-line\">};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L335\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"335\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC335\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L336\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"336\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC336\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(DB x1,DB y1,DB x2,DB y2){return x1*x2+y1*y2;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L337\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"337\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC337\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(cPo a,cPo b){return dot(a.x,a.y,b.x,b.y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L338\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"338\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC338\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(cPo p0,cPo p1,cPo p2){return dot(p1-p0,p2-p0);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L339\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"339\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC339\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(DB x1,DB y1,DB x2,DB y2){return x1*y2-x2*y1;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L340\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"340\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC340\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(cPo a,cPo b){return det(a.x,a.y,b.x,b.y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L341\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"341\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC341\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(cPo p0,cPo p1,cPo p2){return det(p1-p0,p2-p0);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L342\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"342\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC342\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cPo p0,cPo p1){return acos(dot(p0,p1)\/p0.len()\/p1.len());}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L343\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"343\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC343\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cPo p0,cPo p1,cPo p2){return ang(p1-p0,p2-p0);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L344\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"344\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC344\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cPo p0,cPo p1,cPo p2,cPo p3){return ang(p1-p0,p3-p2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L345\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"345\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC345\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(const Po &amp;a, const Po &amp;b){return dist2(a.x-b.x, a.y-b.y);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L346\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"346\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC346\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2&gt; inline int dett(const T1 &amp;x, const T2 &amp;y){return sgn(det(x, y));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L347\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"347\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC347\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3&gt; inline int dett(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z){return sgn(det(x, y, z));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L348\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"348\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC348\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3, class T4&gt; inline int dett(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z, const T4 &amp;w){return sgn(det(x, y, z, w));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L349\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"349\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC349\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2&gt; inline int dott(const T1 &amp;x, const T2 &amp;y){return sgn(dot(x, y));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L350\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"350\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC350\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3&gt; inline int dott(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z){return sgn(dot(x, y, z));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L351\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"351\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC351\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3, class T4&gt; inline int dott(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z, const T4 &amp;w){return sgn(dot(x, y, z, w));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L352\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"352\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC352\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2&gt; inline DB arg(const T1 &amp;x, const T2 &amp;y){DB a=ang(x,y);return~dett(x,y)?a:2*PI-a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L353\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"353\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC353\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3&gt; inline DB arg(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z){DB a=ang(x,y,z);return~dett(x,y,z)?a:2*PI-a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L354\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"354\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC354\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3, class T4&gt; inline DB arg(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z, const T4 &amp;w){DB a=ang(x,y,z,w);return~dett(x,y,z,w)?a:2*PI-a;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L355\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"355\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC355\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2&gt; inline DB dist(const T1 &amp;x, const T2 &amp;y){return sqrt(dist2(x, y));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L356\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"356\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC356\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2, class T3&gt; inline DB dist(const T1 &amp;x, const T2 &amp;y, const T3 &amp;z){return sqrt(dist2(x, y, z));}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L357\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"357\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC357\" class=\"blob-code blob-code-inner js-file-line\">inline Po _1(Po p){return p._1();}inline Po conj(Po p){return p.conj();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L358\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"358\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC358\" class=\"blob-code blob-code-inner js-file-line\">inline Po lt(Po p){return p.lt();}inline Po rt(Po p){return p.rt();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L359\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"359\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC359\" class=\"blob-code blob-code-inner js-file-line\">inline Po rot(Po p,DB a,cPo o=Po()){return p.rot(a,o);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L360\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"360\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC360\" class=\"blob-code blob-code-inner js-file-line\">inline Po operator *(DB k,cPo p){return p*k;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L361\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"361\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC361\" class=\"blob-code blob-code-inner js-file-line\">inline Po operator \/(DB k,cPo p){return conj(p)*k\/p.len2();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L362\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"362\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC362\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L363\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"363\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC363\" class=\"blob-code blob-code-inner js-file-line\">typedef vector&lt;Po&gt; VP;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L364\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"364\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC364\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L365\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"365\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC365\" class=\"blob-code blob-code-inner js-file-line\">struct Line{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L366\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"366\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC366\" class=\"blob-code blob-code-inner js-file-line\">    Po a,b;Line(cPo a=Po(),cPo b=Po()):a(a),b(b){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L367\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"367\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC367\" class=\"blob-code blob-code-inner js-file-line\">    Line(DB x0,DB y0,DB x1,DB y1):a(Po(x0,y0)),b(Po(x1,y1)){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L368\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"368\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC368\" class=\"blob-code blob-code-inner js-file-line\">    Line(cLine l):a(l.a),b(l.b){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L369\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"369\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC369\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L370\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"370\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC370\" class=\"blob-code blob-code-inner js-file-line\">    \/\/Ax+By+C=0<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L371\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"371\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC371\" class=\"blob-code blob-code-inner js-file-line\">    Line(DB A,DB B,DB C){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L372\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"372\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC372\" class=\"blob-code blob-code-inner js-file-line\">        C=-C;if(!::sgn(A))a=Po(0,C\/B),b=Po(1,C\/B);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L373\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"373\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC373\" class=\"blob-code blob-code-inner js-file-line\">        else if(!::sgn(B))a=Po(C\/A,0),b=Po(C\/A,1);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L374\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"374\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC374\" class=\"blob-code blob-code-inner js-file-line\">        else a=Po(0,C\/B),b=Po(1,(C-A)\/B);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L375\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"375\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC375\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L376\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"376\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC376\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L377\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"377\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC377\" class=\"blob-code blob-code-inner js-file-line\">    void in(){a.in(),b.in();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L378\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"378\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC378\" class=\"blob-code blob-code-inner js-file-line\">    inline friend istream&amp;operator&gt;&gt;(istream&amp;i,Line&amp; p){return i&gt;&gt;p.a&gt;&gt;p.b;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L379\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"379\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC379\" class=\"blob-code blob-code-inner js-file-line\">    inline friend ostream&amp;operator&lt;&lt;(ostream&amp;o,Line p){return o&lt;&lt;p.a&lt;&lt;&quot;-&quot;&lt;&lt; p.b;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L380\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"380\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC380\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L381\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"381\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC381\" class=\"blob-code blob-code-inner js-file-line\">    Line operator+(cPo x)const{return Line(a+x,b+x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L382\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"382\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC382\" class=\"blob-code blob-code-inner js-file-line\">    Line operator-(cPo x)const{return Line(a-x,b-x);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L383\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"383\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC383\" class=\"blob-code blob-code-inner js-file-line\">    Line operator*(DB k)const{return Line(a*k,b*k);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L384\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"384\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC384\" class=\"blob-code blob-code-inner js-file-line\">    Line operator\/(DB k)const{return Line(a\/k,b\/k);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L385\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"385\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC385\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L386\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"386\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC386\" class=\"blob-code blob-code-inner js-file-line\">    Po operator*(cLine)const;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L387\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"387\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC387\" class=\"blob-code blob-code-inner js-file-line\">    Po d()const{return b-a;}DB len2()const{return d().len2();}DB len()const{return d().len();}DB arg()const{return d().arg();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L388\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"388\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC388\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L389\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"389\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC389\" class=\"blob-code blob-code-inner js-file-line\">    int sgn(cPo p)const{return dett(a, b, p);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L390\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"390\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC390\" class=\"blob-code blob-code-inner js-file-line\">    int sgn(cLine)const;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L391\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"391\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC391\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L392\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"392\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC392\" class=\"blob-code blob-code-inner js-file-line\">    bool sameSgn(cPo  p1,cPo  p2)const{return sgn(p1)==sgn(p2);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L393\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"393\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC393\" class=\"blob-code blob-code-inner js-file-line\">    void getEquation(DB&amp;K,DB&amp;B)const{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L394\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"394\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC394\" class=\"blob-code blob-code-inner js-file-line\">        K = ::sgn(a.x, b.x) ? (b.y-a.y)\/(b.x-a.x) : OO;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L395\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"395\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC395\" class=\"blob-code blob-code-inner js-file-line\">        B = a.y &#8211; K*a.x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L396\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"396\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC396\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L397\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"397\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC397\" class=\"blob-code blob-code-inner js-file-line\">    void getEquation(DB&amp;A,DB&amp;B,DB&amp;C)const{A=a.y-b.y,B=b.x-a.x,C=det(a, b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L398\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"398\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC398\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L399\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"399\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC399\" class=\"blob-code blob-code-inner js-file-line\">    Line&amp;push(DB r){ \/\/ \u6b63\u6570\u53f3\u624b\u87ba\u65cb\u5411\u91cc<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L400\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"400\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC400\" class=\"blob-code blob-code-inner js-file-line\">        Po v=d()._1().lt()*r;a+=v,b+=v; rTs;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L401\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"401\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC401\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L402\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"402\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC402\" class=\"blob-code blob-code-inner js-file-line\">};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L403\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"403\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC403\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L404\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"404\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC404\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(cLine l1,cLine l2){return dot(l1.d(),l2.d());}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L405\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"405\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC405\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(cLine l,cPo p){return dot(l.a,l.b,p);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L406\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"406\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC406\" class=\"blob-code blob-code-inner js-file-line\">inline DB dot(cPo p,cLine l){return dot(p,l.a,l.b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L407\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"407\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC407\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(cLine l1,cLine l2){return det(l1.d(),l2.d());}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L408\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"408\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC408\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(cLine l,cPo p){return det(l.a,l.b,p);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L409\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"409\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC409\" class=\"blob-code blob-code-inner js-file-line\">inline DB det(cPo p,cLine l){return det(p,l.a,l.b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L410\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"410\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC410\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cLine l0,cLine l1){return ang(l0.d(),l1.d());}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L411\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"411\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC411\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cLine l,cPo p){return ang(l.a,l.b,p);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L412\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"412\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC412\" class=\"blob-code blob-code-inner js-file-line\">inline DB ang(cPo p,cLine l){return ang(p,l.a,l.b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L413\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"413\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC413\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L414\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"414\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC414\" class=\"blob-code blob-code-inner js-file-line\">inline int Line::sgn(cLine l)const{return dett(Ts, l);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L415\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"415\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC415\" class=\"blob-code blob-code-inner js-file-line\">inline Po Line::operator*(cLine l)const{return a+d()*det(a,l)\/det(Ts,l);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L416\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"416\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC416\" class=\"blob-code blob-code-inner js-file-line\">inline Po operator&amp;(cPo p,cLine l){return l*Line(p,p+l.d().lt());}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L417\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"417\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC417\" class=\"blob-code blob-code-inner js-file-line\">inline Po operator%(cPo p,cLine l){return p&amp;l*2-p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L418\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"418\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC418\" class=\"blob-code blob-code-inner js-file-line\">inline Line push(Line l, DB r){return l.push(r);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L419\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"419\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC419\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L420\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"420\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC420\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L421\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"421\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC421\" class=\"blob-code blob-code-inner js-file-line\">struct Seg: public Line{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L422\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"422\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC422\" class=\"blob-code blob-code-inner js-file-line\">    Seg(cPo a=Po(),cPo b=Po()):Line(a,b){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L423\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"423\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC423\" class=\"blob-code blob-code-inner js-file-line\">    Seg(DB x0,DB y0,DB x1,DB y1):Line(x0,y0,x1,y1){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L424\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"424\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC424\" class=\"blob-code blob-code-inner js-file-line\">    Seg(cLine l):Line(l){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L425\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"425\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC425\" class=\"blob-code blob-code-inner js-file-line\">    Seg(const Po &amp;a,DB alpha):Line(a,alpha){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L426\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"426\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC426\" class=\"blob-code blob-code-inner js-file-line\">    Seg(DB A,DB B,DB C):Line(A,B,C){}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L427\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"427\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC427\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L428\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"428\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC428\" class=\"blob-code blob-code-inner js-file-line\">    inline int sgn(cPo p)const;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L429\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"429\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC429\" class=\"blob-code blob-code-inner js-file-line\">    inline bool qrt(cSeg l)const;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L430\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"430\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC430\" class=\"blob-code blob-code-inner js-file-line\">    inline int sgn(cSeg l)const;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L431\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"431\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC431\" class=\"blob-code blob-code-inner js-file-line\">};<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L432\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"432\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC432\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L433\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"433\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC433\" class=\"blob-code blob-code-inner js-file-line\"> \/\/ -1\u4e0d\u76f8\u4ea4 0\u76f8\u4ea4\uff08\u4e0d\u89c4\u8303\uff09 1\u76f8\u4ea4\uff08\u89c4\u8303\uff09<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L434\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"434\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC434\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L435\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"435\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC435\" class=\"blob-code blob-code-inner js-file-line\">inline int Seg::sgn(cPo p)const{return -dott(p,a,b);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L436\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"436\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC436\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L437\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"437\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC437\" class=\"blob-code blob-code-inner js-file-line\">\/\/ quick_rejection_test<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L438\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"438\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC438\" class=\"blob-code blob-code-inner js-file-line\">inline bool Seg::qrt(cSeg l)const{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L439\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"439\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC439\" class=\"blob-code blob-code-inner js-file-line\">    return min(a.x,b.x)&lt;=max(l.a.x,l.b.x)&amp;&amp;min(l.a.x,l.b.x)&lt;=max(a.x,b.x)&amp;&amp;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L440\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"440\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC440\" class=\"blob-code blob-code-inner js-file-line\">        min(a.y,b.y)&lt;=max(l.a.y,l.b.y)&amp;&amp;min(l.a.y,l.b.y)&lt;=max(a.y,b.y);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L441\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"441\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC441\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L442\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"442\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC442\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L443\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"443\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC443\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L444\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"444\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC444\" class=\"blob-code blob-code-inner js-file-line\">inline int Seg::sgn(cSeg l)const{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L445\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"445\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC445\" class=\"blob-code blob-code-inner js-file-line\">    if (!qrt(l)) return -1;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L446\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"446\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC446\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L447\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"447\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC447\" class=\"blob-code blob-code-inner js-file-line\">    \/*return<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L448\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"448\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC448\" class=\"blob-code blob-code-inner js-file-line\">        (dett(a,b,l.a)*dett(a,b,l.b)&lt;=0 &amp;&amp;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L449\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"449\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC449\" class=\"blob-code blob-code-inner js-file-line\">        dett(l.a,l.b,a)*dett(l.a,l.b,b)&lt;=0)?1:-1;*\/<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L450\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"450\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC450\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L451\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"451\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC451\" class=\"blob-code blob-code-inner js-file-line\">    int d1=dett(a,b,l.a),d2=dett(a,b,l.b),d3=dett(l.a,l.b,a),d4=dett(l.a,l.b,b);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L452\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"452\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC452\" class=\"blob-code blob-code-inner js-file-line\">    if ((d1^d2)==-2&amp;&amp;(d3^d4)==-2)return 1;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L453\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"453\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC453\" class=\"blob-code blob-code-inner js-file-line\">    return ((!d1&amp;&amp;dott(l.a-a,l.a-b)&lt;=0)||(!d2&amp;&amp;dott(l.b-a,l.b-b)&lt;=0)||<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L454\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"454\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC454\" class=\"blob-code blob-code-inner js-file-line\">            (!d3&amp;&amp;dott(a-l.a,a-l.b)&lt;=0)||(!d4&amp;&amp;dott(b-l.a,b-l.b)&lt;=0))?0:-1;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L455\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"455\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC455\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L456\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"456\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC456\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L457\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"457\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC457\" class=\"blob-code blob-code-inner js-file-line\">\/\/inline DB dist2(cLine l,cPo p){return sqr(fabs(dot(lt(l.d()), p-l.a)))\/l.len2();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L458\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"458\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC458\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(cLine l,cPo p){return sqr(fabs(det(l.d(), p-l.a)))\/l.len2();}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L459\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"459\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC459\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L460\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"460\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC460\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(cLine l1,cLine l2){return dett(l1,l2)?0:dist2(l1,l2.a);}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L461\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"461\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC461\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L462\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"462\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC462\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(cSeg l,cPo p){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L463\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"463\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC463\" class=\"blob-code blob-code-inner js-file-line\">    Po pa = p &#8211; l.a, pb = p &#8211; l.b;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L464\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"464\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC464\" class=\"blob-code blob-code-inner js-file-line\">    if (dott(l.d(), pa) &lt;= 0) return pa.len2();<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L465\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"465\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC465\" class=\"blob-code blob-code-inner js-file-line\">    if (dott(l.d(), pb) &gt;= 0) return pb.len2();<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L466\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"466\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC466\" class=\"blob-code blob-code-inner js-file-line\">    return dist2(Line(l), p);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L467\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"467\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC467\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L468\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"468\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC468\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L469\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"469\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC469\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L470\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"470\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC470\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(cSeg s,cLine l){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L471\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"471\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC471\" class=\"blob-code blob-code-inner js-file-line\">    Po v1=s.a-l.a,v2=s.b-l.a;DB d1=det(l.d(),v1),d2=det(l.d(),v2);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L472\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"472\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC472\" class=\"blob-code blob-code-inner js-file-line\">    return sgn(d1)!=sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2)))\/l.len2();<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L473\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"473\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC473\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L474\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"474\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC474\" class=\"blob-code blob-code-inner js-file-line\">inline DB dist2(cSeg l1,cSeg l2){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L475\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"475\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC475\" class=\"blob-code blob-code-inner js-file-line\">    if (~l1.sgn(l2)) return 0;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L476\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"476\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC476\" class=\"blob-code blob-code-inner js-file-line\">    else return min(dist2(l2,l1.a), dist2(l2,l1.b), dist2(l1,l2.a), dist2(l1,l2.b));<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L477\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"477\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC477\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L478\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"478\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC478\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T1, class T2&gt; inline DB dist2(const T1&amp; a, const T2&amp; b){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L479\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"479\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC479\" class=\"blob-code blob-code-inner js-file-line\">    return dist2(b, a);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L480\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"480\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC480\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L481\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"481\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC481\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L482\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"482\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC482\" class=\"blob-code blob-code-inner js-file-line\">} using namespace CG;\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L483\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"483\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC483\" class=\"blob-code blob-code-inner js-file-line\">\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L484\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"484\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC484\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L485\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"485\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC485\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L486\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"486\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC486\" class=\"blob-code blob-code-inner js-file-line\">\/** I\/O Accelerator Interface .. **\/ \/\/{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L487\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"487\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC487\" class=\"blob-code blob-code-inner js-file-line\">#define g (c=getchar())<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L488\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"488\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC488\" class=\"blob-code blob-code-inner js-file-line\">#define d isdigit(g)<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L489\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"489\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC489\" class=\"blob-code blob-code-inner js-file-line\">#define p x=x*10+c-&#39;0&#39;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L490\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"490\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC490\" class=\"blob-code blob-code-inner js-file-line\">#define n x=x*10+&#39;0&#39;-c<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L491\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"491\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC491\" class=\"blob-code blob-code-inner js-file-line\">#define pp l\/=10,p<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L492\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"492\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC492\" class=\"blob-code blob-code-inner js-file-line\">#define nn l\/=10,n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L493\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"493\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC493\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; RD(T &amp;x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L494\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"494\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC494\" class=\"blob-code blob-code-inner js-file-line\">    char c;while(!d);x=c-&#39;0&#39;;while(d)p;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L495\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"495\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC495\" class=\"blob-code blob-code-inner js-file-line\">    return x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L496\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"496\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC496\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L497\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"497\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC497\" class=\"blob-code blob-code-inner js-file-line\">template&lt;class T&gt; inline T&amp; RDD(T &amp;x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L498\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"498\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC498\" class=\"blob-code blob-code-inner js-file-line\">    char c;while(g,c!=&#39;-&#39;&amp;&amp;!isdigit(c));<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L499\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"499\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC499\" class=\"blob-code blob-code-inner js-file-line\">    if (c==&#39;-&#39;){x=&#39;0&#39;-g;while(d)n;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L500\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"500\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC500\" class=\"blob-code blob-code-inner js-file-line\">    else{x=c-&#39;0&#39;;while(d)p;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L501\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"501\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC501\" class=\"blob-code blob-code-inner js-file-line\">    return x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L502\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"502\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC502\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L503\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"503\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC503\" class=\"blob-code blob-code-inner js-file-line\">inline DB&amp; RF(DB &amp;x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L504\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"504\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC504\" class=\"blob-code blob-code-inner js-file-line\">    \/\/scanf(&quot;%lf&quot;, &amp;x);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L505\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"505\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC505\" class=\"blob-code blob-code-inner js-file-line\">    char c;while(g,c!=&#39;-&#39;&amp;&amp;c!=&#39;.&#39;&amp;&amp;!isdigit(c));<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L506\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"506\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC506\" class=\"blob-code blob-code-inner js-file-line\">    if(c==&#39;-&#39;)if(g==&#39;.&#39;){x=0;DB l=1;while(d)nn;x*=l;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L507\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"507\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC507\" class=\"blob-code blob-code-inner js-file-line\">        else{x=&#39;0&#39;-c;while(d)n;if(c==&#39;.&#39;){DB l=1;while(d)nn;x*=l;}}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L508\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"508\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC508\" class=\"blob-code blob-code-inner js-file-line\">    else if(c==&#39;.&#39;){x=0;DB l=1;while(d)pp;x*=l;}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L509\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"509\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC509\" class=\"blob-code blob-code-inner js-file-line\">        else{x=c-&#39;0&#39;;while(d)p;if(c==&#39;.&#39;){DB l=1;while(d)pp;x*=l;}}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L510\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"510\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC510\" class=\"blob-code blob-code-inner js-file-line\">    return x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L511\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"511\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC511\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L512\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"512\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC512\" class=\"blob-code blob-code-inner js-file-line\">#undef nn<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L513\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"513\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC513\" class=\"blob-code blob-code-inner js-file-line\">#undef pp<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L514\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"514\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC514\" class=\"blob-code blob-code-inner js-file-line\">#undef n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L515\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"515\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC515\" class=\"blob-code blob-code-inner js-file-line\">#undef p<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L516\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"516\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC516\" class=\"blob-code blob-code-inner js-file-line\">#undef d<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L517\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"517\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC517\" class=\"blob-code blob-code-inner js-file-line\">#undef g<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L518\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"518\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC518\" class=\"blob-code blob-code-inner js-file-line\">inline char* RS(char *s){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L519\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"519\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC519\" class=\"blob-code blob-code-inner js-file-line\">    \/\/gets(s);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L520\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"520\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC520\" class=\"blob-code blob-code-inner js-file-line\">    scanf(&quot;%s&quot;, s);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L521\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"521\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC521\" class=\"blob-code blob-code-inner js-file-line\">    return s;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L522\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"522\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC522\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L523\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"523\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC523\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L524\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"524\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC524\" class=\"blob-code blob-code-inner js-file-line\">LL last_ans; int Case; template&lt;class T&gt; inline void OT(const T &amp;x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L525\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"525\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC525\" class=\"blob-code blob-code-inner js-file-line\">    \/\/printf(&quot;Case #%d: &quot;, ++Case);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L526\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"526\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC526\" class=\"blob-code blob-code-inner js-file-line\">    \/\/printf(&quot;%lld\\n&quot;, x);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L527\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"527\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC527\" class=\"blob-code blob-code-inner js-file-line\">    \/\/printf(&quot;%.4f\\n&quot;, x);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L528\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"528\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC528\" class=\"blob-code blob-code-inner js-file-line\">    printf(&quot;%d\\n&quot;, x);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L529\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"529\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC529\" class=\"blob-code blob-code-inner js-file-line\">    \/\/cout &lt;&lt; x &lt;&lt; endl;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L530\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"530\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC530\" class=\"blob-code blob-code-inner js-file-line\">    \/\/last_ans = x;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L531\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"531\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC531\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L532\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"532\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC532\" class=\"blob-code blob-code-inner js-file-line\">\/\/}<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L533\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"533\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC533\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L534\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"534\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC534\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L535\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"535\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC535\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L536\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"536\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC536\" class=\"blob-code blob-code-inner js-file-line\">\/\/}\/* &#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;&#8230;. *\/<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L537\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"537\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC537\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L538\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"538\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC538\" class=\"blob-code blob-code-inner js-file-line\">namespace BIT{<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L539\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"539\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC539\" class=\"blob-code blob-code-inner js-file-line\">    const int N = int(5e4) + 9, M = int(2e5) + 9;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L540\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"540\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC540\" class=\"blob-code blob-code-inner js-file-line\">    int A[N], B[N], P[N], C[N], n;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L541\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"541\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC541\" class=\"blob-code blob-code-inner js-file-line\">    VII Q[N]; int ans[M], m;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L542\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"542\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC542\" class=\"blob-code blob-code-inner js-file-line\">    void Add(int x, int d){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L543\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"543\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC543\" class=\"blob-code blob-code-inner js-file-line\">        for (;x&lt;=n;x+=low_bit(x)) C[x] += d;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L544\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"544\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC544\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L545\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"545\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC545\" class=\"blob-code blob-code-inner js-file-line\">    int Sum(int x){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L546\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"546\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC546\" class=\"blob-code blob-code-inner js-file-line\">        int res = 0; for (;x;x^=low_bit(x)) res += C[x];<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L547\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"547\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC547\" class=\"blob-code blob-code-inner js-file-line\">        return res;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L548\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"548\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC548\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L549\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"549\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC549\" class=\"blob-code blob-code-inner js-file-line\">} using namespace BIT;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L550\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"550\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC550\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L551\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"551\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC551\" class=\"blob-code blob-code-inner js-file-line\">int main(){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L552\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"552\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC552\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L553\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"553\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC553\" class=\"blob-code blob-code-inner js-file-line\">#ifndef ONLINE_JUDGE<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L554\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"554\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC554\" class=\"blob-code blob-code-inner js-file-line\">    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L555\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"555\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC555\" class=\"blob-code blob-code-inner js-file-line\">    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L556\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"556\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC556\" class=\"blob-code blob-code-inner js-file-line\">#endif<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L557\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"557\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC557\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L558\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"558\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC558\" class=\"blob-code blob-code-inner js-file-line\">    REP_1_C(i, RD(n)) B[i] = RD(A[i]); sort(B+1, B+n+1), m = unique(B+1, B+n+1) &#8211; B;<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L559\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"559\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC559\" class=\"blob-code blob-code-inner js-file-line\">    REP_1(i, n) A[i] = lower_bound(B+1, B+m, A[i]) &#8211; B; REP_C(i, RD(m)){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L560\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"560\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC560\" class=\"blob-code blob-code-inner js-file-line\">        int l, r; RD(l, r);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L561\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"561\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC561\" class=\"blob-code blob-code-inner js-file-line\">        Q[l].PB(MP(r, i));<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L562\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"562\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC562\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L563\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"563\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC563\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L564\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"564\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC564\" class=\"blob-code blob-code-inner js-file-line\">    DWN_1(i, n, 1){<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L565\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"565\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC565\" class=\"blob-code blob-code-inner js-file-line\">        if (P[A[i]]) Add(P[A[i]], -1); Add(P[A[i]] = i, 1);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L566\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"566\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC566\" class=\"blob-code blob-code-inner js-file-line\">        ECH(it, Q[i]) ans[it-&gt;se] = Sum(it-&gt;fi);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L567\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"567\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC567\" class=\"blob-code blob-code-inner js-file-line\">    }<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L568\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"568\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC568\" class=\"blob-code blob-code-inner js-file-line\">\n<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L569\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"569\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC569\" class=\"blob-code blob-code-inner js-file-line\">    REP(i, m) OT(ans[i]);<\/td>\n<\/tr>\n<tr>\n<td id=\"file-bzoj_1878-cpp-L570\" class=\"blob-num js-line-number js-blob-rnum\" data-line-number=\"570\"><\/td>\n<td id=\"file-bzoj_1878-cpp-LC570\" class=\"blob-code blob-code-inner js-file-line\">}<\/td>\n<\/tr>\n<\/table>\n<\/div><\/div>\n<\/p><\/div>\n<\/div><\/div>\n<div class=\"gist-meta\">\n        <a href=\"https:\/\/gist.github.com\/lychees\/6978412\/raw\/c953eb68ed9e2568583fafded5fa5099aa44716f\/BZOJ_1878.cpp\" style=\"float:right\" class=\"Link--inTextBlock\">view raw<\/a><br \/>\n        <a href=\"https:\/\/gist.github.com\/lychees\/6978412#file-bzoj_1878-cpp\" class=\"Link--inTextBlock\"><br \/>\n          BZOJ_1878.cpp<br \/>\n        <\/a><br \/>\n        hosted with &#10084; by <a class=\"Link--inTextBlock\" href=\"https:\/\/github.com\">GitHub<\/a>\n      <\/div>\n<\/p><\/div>\n<\/div>\n<p><bk><bk><bk><bk><br \/>\n<bk><bk><bk><bk><\/p>\n<h3>External link :<\/h3>\n<p>http:\/\/user.qzone.qq.com\/251815992\/blog\/1355245026<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u7ed9\u5b9a\u6570\u5217{Ai}\uff0c\u79bb\u7ebf\u8be2\u95ee\u533a\u95f4\u76f8\u5f02\u6570\u5b57\u7684\u6570\u76ee\u3002\u6570\u5217\u957f\u5ea6 n\uff0c\u8be2\u95ee m \u6b21\u3002 \uff08n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-71","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-19","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/71","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=71"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/71\/revisions"}],"predecessor-version":[{"id":838,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/71\/revisions\/838"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=71"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=71"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}