daily pastebin goal
61%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedOutputStream;
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.PrintWriter;
  6. import java.math.BigInteger;
  7. import java.util.AbstractMap;
  8. import java.util.ArrayList;
  9. import java.util.Arrays;
  10. import java.util.Collection;
  11. import java.util.Comparator;
  12. import java.util.HashMap;
  13. import java.util.Iterator;
  14. import java.util.LinkedList;
  15. import java.util.List;
  16. import java.util.Map;
  17. import java.util.NoSuchElementException;
  18. import java.util.Set;
  19. import java.util.SortedMap;
  20. import java.util.SortedSet;
  21. import java.util.Stack;
  22. import java.util.StringTokenizer;
  23. import java.util.function.BiConsumer;
  24. import java.util.function.Consumer;
  25. import java.util.function.Function;
  26. import java.util.function.Supplier;
  27. import java.util.stream.Stream;
  28.  
  29. public class Main
  30. {
  31.     public static final long[] POWER2 = generatePOWER2();
  32.     public static final IteratorBuffer<Long> ITERATOR_BUFFER_PRIME = new IteratorBuffer<>(streamPrime(1000000).iterator());
  33.     private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  34.     private static StringTokenizer stringTokenizer = null;
  35.     private static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  36.  
  37.     interface BiFunctionResult<Type0, Type1, TypeResult>
  38.     {
  39.         TypeResult apply(Type0 x0, Type1 x1, TypeResult x2);
  40.     }
  41.  
  42.     static class Array<Type> implements Iterable<Type>
  43.     {
  44.         private Object[] array;
  45.  
  46.         public Array(int size)
  47.         {
  48.             this.array = new Object[size];
  49.         }
  50.  
  51.         public Array(int size, Type element)
  52.         {
  53.             this(size);
  54.             Arrays.fill(this.array, element);
  55.         }
  56.  
  57.         public Array(Array<Type> array, Type element)
  58.         {
  59.             this(array.size() + 1);
  60.             for (int index = 0; index < array.size(); index++)
  61.             {
  62.                 set(index, array.get(index));
  63.             }
  64.             set(size() - 1, element);
  65.         }
  66.  
  67.         public Array(List<Type> list)
  68.         {
  69.             this(list.size());
  70.             int index = 0;
  71.             for (Type element : list)
  72.             {
  73.                 set(index, element);
  74.                 index += 1;
  75.             }
  76.         }
  77.  
  78.         public Type get(int index)
  79.         {
  80.             return (Type) this.array[index];
  81.         }
  82.  
  83.         public Array set(int index, Type value)
  84.         {
  85.             this.array[index] = value;
  86.             return this;
  87.         }
  88.  
  89.         public int size()
  90.         {
  91.             return this.array.length;
  92.         }
  93.  
  94.         public List<Type> toList()
  95.         {
  96.             List<Type> result = new ArrayList<>();
  97.             for (Type element : this)
  98.             {
  99.                 result.add(element);
  100.             }
  101.             return result;
  102.         }
  103.  
  104.         @Override
  105.         public Iterator<Type> iterator()
  106.         {
  107.             return new Iterator<Type>()
  108.             {
  109.                 int index = 0;
  110.  
  111.                 @Override
  112.                 public boolean hasNext()
  113.                 {
  114.                     return this.index < size();
  115.                 }
  116.  
  117.                 @Override
  118.                 public Type next()
  119.                 {
  120.                     Type result = Array.this.get(index);
  121.                     index += 1;
  122.                     return result;
  123.                 }
  124.             };
  125.         }
  126.  
  127.         @Override
  128.         public String toString()
  129.         {
  130.             return "[" + A_423.toString(this, ", ") + "]";
  131.         }
  132.     }
  133.  
  134.     static abstract class Edge<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>>
  135.     {
  136.         public final TypeVertex vertex0;
  137.         public final TypeVertex vertex1;
  138.         public final boolean bidirectional;
  139.  
  140.         public Edge(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
  141.         {
  142.             this.vertex0 = vertex0;
  143.             this.vertex1 = vertex1;
  144.             this.bidirectional = bidirectional;
  145.             this.vertex0.edges.add(getThis());
  146.             if (this.bidirectional)
  147.             {
  148.                 this.vertex1.edges.add(getThis());
  149.             }
  150.         }
  151.  
  152.         public TypeVertex other(Vertex<TypeVertex, TypeEdge> vertex)
  153.         {
  154.             TypeVertex result;
  155.             if (vertex0 == vertex)
  156.             {
  157.                 result = vertex1;
  158.             }
  159.             else
  160.             {
  161.                 result = vertex0;
  162.             }
  163.             return result;
  164.         }
  165.  
  166.         public abstract TypeEdge getThis();
  167.  
  168.         public void remove()
  169.         {
  170.             this.vertex0.edges.remove(getThis());
  171.             if (this.bidirectional)
  172.             {
  173.                 this.vertex1.edges.remove(getThis());
  174.             }
  175.         }
  176.  
  177.         @Override
  178.         public String toString()
  179.         {
  180.             return this.vertex0 + "->" + this.vertex1;
  181.         }
  182.     }
  183.  
  184.     public static class EdgeDefault<TypeVertex extends Vertex<TypeVertex, EdgeDefault<TypeVertex>>> extends Edge<TypeVertex, EdgeDefault<TypeVertex>>
  185.     {
  186.         public EdgeDefault(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
  187.         {
  188.             super(vertex0, vertex1, bidirectional);
  189.         }
  190.  
  191.         @Override
  192.         public EdgeDefault<TypeVertex> getThis()
  193.         {
  194.             return this;
  195.         }
  196.     }
  197.  
  198.     public static class Vertex<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>> implements Comparable<Vertex<? super TypeVertex, ? super TypeEdge>>
  199.     {
  200.         public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>> void depthFirstSearch(
  201.                 Array<TypeVertex> vertices,
  202.                 int indexVertexStart,
  203.                 BiConsumer<TypeVertex, TypeEdge> functionPreVisit,
  204.                 BiConsumer<TypeVertex, TypeEdge> functionInVisit,
  205.                 BiConsumer<TypeVertex, TypeEdge> functionPostVisit
  206.         )
  207.         {
  208.             TypeVertex vertexTo;
  209.             TypeEdge edgeTo;
  210.             boolean[] isOnStack = new boolean[vertices.size()];
  211.             Stack<Operation> stackOperations = new Stack<>();
  212.             Stack<TypeVertex> stackVertices = new Stack<>();
  213.             Stack<TypeEdge> stackEdges = new Stack<>();
  214.  
  215.             TypeVertex vertexStart = vertices.get(indexVertexStart);
  216.             stackOperations.push(Operation.EXPAND);
  217.             stackVertices.push(vertexStart);
  218.             stackEdges.push(null);
  219.             isOnStack[vertexStart.index] = true;
  220.             while (!stackOperations.isEmpty())
  221.             {
  222.                 Operation operation = stackOperations.pop();
  223.                 TypeVertex vertex = stackVertices.pop();
  224.                 TypeEdge edge = stackEdges.pop();
  225.                 switch (operation)
  226.                 {
  227.                     case INVISIT:
  228.                         functionInVisit.accept(vertex, edge);
  229.                         break;
  230.                     case POSTVISIT:
  231.                         functionPostVisit.accept(vertex, edge);
  232.                         break;
  233.                     case EXPAND:
  234.                         stackOperations.push(Operation.POSTVISIT);
  235.                         stackVertices.push(vertex);
  236.                         stackEdges.push(edge);
  237.                         Integer indexTo = null;
  238.                         for (int index = 0; indexTo == null && index < vertex.edges.size(); index++)
  239.                         {
  240.                             edgeTo = vertex.edges.get(index);
  241.                             vertexTo = edgeTo.other(vertex);
  242.                             if (!isOnStack[vertexTo.index])
  243.                             {
  244.                                 indexTo = index;
  245.                             }
  246.                         }
  247.                         if (indexTo != null)
  248.                         {
  249.                             edgeTo = vertex.edges.get(indexTo);
  250.                             vertexTo = edgeTo.other(vertex);
  251.                             stackOperations.push(Operation.EXPAND);
  252.                             stackVertices.push(vertexTo);
  253.                             stackEdges.push(edgeTo);
  254.                             isOnStack[vertexTo.index] = true;
  255.                             for (int index = indexTo + 1; index < vertex.edges.size(); index++)
  256.                             {
  257.                                 edgeTo = vertex.edges.get(index);
  258.                                 vertexTo = edgeTo.other(vertex);
  259.                                 if (!isOnStack[vertexTo.index])
  260.                                 {
  261.                                     stackOperations.push(Operation.INVISIT);
  262.                                     stackVertices.push(vertex);
  263.                                     stackEdges.push(edge);
  264.                                     stackOperations.push(Operation.EXPAND);
  265.                                     stackVertices.push(vertexTo);
  266.                                     stackEdges.push(edgeTo);
  267.                                     isOnStack[vertexTo.index] = true;
  268.                                 }
  269.                             }
  270.                         }
  271.                         functionPreVisit.accept(vertex, edge);
  272.                         break;
  273.                 }
  274.             }
  275.         }
  276.  
  277.         public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>> void depthFirstSearch(
  278.                 Array<TypeVertex> vertices,
  279.                 int indexVertexStart,
  280.                 Consumer<TypeVertex> functionPreVisit,
  281.                 Consumer<TypeVertex> functionInVisit,
  282.                 Consumer<TypeVertex> functionPostVisit
  283.         )
  284.         {
  285.             depthFirstSearch(
  286.                     vertices,
  287.                     indexVertexStart,
  288.                     (vertex, edge) -> functionPreVisit.accept(vertex),
  289.                     (vertex, edge) -> functionInVisit.accept(vertex),
  290.                     (vertex, edge) -> functionPostVisit.accept(vertex)
  291.             );
  292.         }
  293.  
  294.         public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult breadthFirstSearch(
  295.                 TypeVertex vertex,
  296.                 TypeEdge edge,
  297.                 BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
  298.                 Array<Boolean> visited,
  299.                 FIFO<TypeVertex> verticesNext,
  300.                 FIFO<TypeEdge> edgesNext,
  301.                 TypeResult result
  302.         )
  303.         {
  304.             if (!visited.get(vertex.index))
  305.             {
  306.                 visited.set(vertex.index, true);
  307.                 result = function.apply(vertex, edge, result);
  308.                 for (TypeEdge edgeNext : vertex.edges)
  309.                 {
  310.                     TypeVertex vertexNext = edgeNext.other(vertex);
  311.                     if (!visited.get(vertexNext.index))
  312.                     {
  313.                         verticesNext.push(vertexNext);
  314.                         edgesNext.push(edgeNext);
  315.                     }
  316.                 }
  317.             }
  318.             return result;
  319.         }
  320.  
  321.         public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult breadthFirstSearch(
  322.                 Array<TypeVertex> vertices,
  323.                 int indexVertexStart,
  324.                 BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
  325.                 TypeResult result
  326.         )
  327.         {
  328.             Array<Boolean> visited = new Array<>(vertices.size(), false);
  329.             FIFO<TypeVertex> verticesNext = new FIFO<>();
  330.             verticesNext.push(vertices.get(indexVertexStart));
  331.             FIFO<TypeEdge> edgesNext = new FIFO<>();
  332.             edgesNext.push(null);
  333.             while (!verticesNext.isEmpty())
  334.             {
  335.                 result = breadthFirstSearch(verticesNext.pop(), edgesNext.pop(), function, visited, verticesNext, edgesNext, result);
  336.             }
  337.             return result;
  338.         }
  339.  
  340.         public final int index;
  341.         public final List<TypeEdge> edges;
  342.  
  343.         public Vertex(int index)
  344.         {
  345.             this.index = index;
  346.             this.edges = new ArrayList<>();
  347.         }
  348.  
  349.         @Override
  350.         public int compareTo(Vertex<? super TypeVertex, ? super TypeEdge> that)
  351.         {
  352.             return Integer.compare(this.index, that.index);
  353.         }
  354.  
  355.         @Override
  356.         public String toString()
  357.         {
  358.             return "" + this.index;
  359.         }
  360.  
  361.         enum Operation
  362.         {
  363.             INVISIT, POSTVISIT, EXPAND
  364.         }
  365.     }
  366.  
  367.     public static class VertexDefault<TypeEdge extends Edge<VertexDefault<TypeEdge>, TypeEdge>> extends Vertex<VertexDefault<TypeEdge>, TypeEdge>
  368.     {
  369.         public VertexDefault(int index)
  370.         {
  371.             super(index);
  372.         }
  373.     }
  374.  
  375.     public static class VertexDefaultDefault extends Vertex<VertexDefaultDefault, EdgeDefaultDefault>
  376.     {
  377.         public static Array<VertexDefaultDefault> vertices(int n)
  378.         {
  379.             Array<VertexDefaultDefault> result = new Array<>(n);
  380.             for (int index = 0; index < n; index++)
  381.             {
  382.                 result.set(index, new VertexDefaultDefault(index));
  383.             }
  384.             return result;
  385.         }
  386.  
  387.         public VertexDefaultDefault(int index)
  388.         {
  389.             super(index);
  390.         }
  391.     }
  392.  
  393.     public static class EdgeDefaultDefault extends Edge<VertexDefaultDefault, EdgeDefaultDefault>
  394.     {
  395.         public EdgeDefaultDefault(VertexDefaultDefault vertex0, VertexDefaultDefault vertex1, boolean bidirectional)
  396.         {
  397.             super(vertex0, vertex1, bidirectional);
  398.         }
  399.  
  400.         @Override
  401.         public EdgeDefaultDefault getThis()
  402.         {
  403.             return this;
  404.         }
  405.     }
  406.  
  407.     public static class Tuple2<Type0, Type1>
  408.     {
  409.         public final Type0 v0;
  410.         public final Type1 v1;
  411.  
  412.         public Tuple2(Type0 v0, Type1 v1)
  413.         {
  414.             this.v0 = v0;
  415.             this.v1 = v1;
  416.         }
  417.  
  418.         @Override
  419.         public String toString()
  420.         {
  421.             return "(" + this.v0 + ", " + this.v1 + ")";
  422.         }
  423.     }
  424.  
  425.     static class Wrapper<Type>
  426.     {
  427.         public Type value;
  428.  
  429.         public Wrapper(Type value)
  430.         {
  431.             this.value = value;
  432.         }
  433.  
  434.         public Type get()
  435.         {
  436.             return this.value;
  437.         }
  438.  
  439.         public void set(Type value)
  440.         {
  441.             this.value = value;
  442.         }
  443.  
  444.         @Override
  445.         public String toString()
  446.         {
  447.             return this.value.toString();
  448.         }
  449.     }
  450.  
  451.     public static class Tuple3<Type0, Type1, Type2>
  452.     {
  453.         public final Type0 v0;
  454.         public final Type1 v1;
  455.         public final Type2 v2;
  456.  
  457.         public Tuple3(Type0 v0, Type1 v1, Type2 v2)
  458.         {
  459.             this.v0 = v0;
  460.             this.v1 = v1;
  461.             this.v2 = v2;
  462.         }
  463.  
  464.         @Override
  465.         public String toString()
  466.         {
  467.             return "(" + this.v0 + ", " + this.v1 + ", " + this.v2 + ")";
  468.         }
  469.     }
  470.  
  471.     public static class Tuple2Comparable<Type0 extends Comparable<? super Type0>, Type1 extends Comparable<? super Type1>> extends Tuple2<Type0, Type1> implements Comparable<Tuple2Comparable<Type0, Type1>>
  472.     {
  473.         public Tuple2Comparable(Type0 v0, Type1 v1)
  474.         {
  475.             super(v0, v1);
  476.         }
  477.  
  478.         @Override
  479.         public int compareTo(Tuple2Comparable<Type0, Type1> that)
  480.         {
  481.             int result = this.v0.compareTo(that.v0);
  482.             if (result == 0)
  483.             {
  484.                 result = this.v1.compareTo(that.v1);
  485.             }
  486.             return result;
  487.         }
  488.     }
  489.  
  490.     public static class SingleLinkedList<Type>
  491.     {
  492.         public final Type element;
  493.         public SingleLinkedList<Type> next;
  494.  
  495.         public SingleLinkedList(Type element, SingleLinkedList<Type> next)
  496.         {
  497.             this.element = element;
  498.             this.next = next;
  499.         }
  500.  
  501.         public void toCollection(Collection<Type> collection)
  502.         {
  503.             if (this.next != null)
  504.             {
  505.                 this.next.toCollection(collection);
  506.             }
  507.             collection.add(this.element);
  508.         }
  509.     }
  510.  
  511.     public static class Node<Type>
  512.     {
  513.         public static <Type> Node<Type> balance(Node<Type> result)
  514.         {
  515.             while (result != null && 1 < Math.abs(height(result.left) - height(result.right)))
  516.             {
  517.                 if (height(result.left) < height(result.right))
  518.                 {
  519.                     Node<Type> right = result.right;
  520.                     if (height(right.right) < height(right.left))
  521.                     {
  522.                         result = new Node<>(result.value, result.left, right.rotateRight());
  523.                     }
  524.                     result = result.rotateLeft();
  525.                 }
  526.                 else
  527.                 {
  528.                     Node<Type> left = result.left;
  529.                     if (height(left.left) < height(left.right))
  530.                     {
  531.                         result = new Node<>(result.value, left.rotateLeft(), result.right);
  532.                     }
  533.                     result = result.rotateRight();
  534.                 }
  535.             }
  536.             return result;
  537.         }
  538.  
  539.         public static <Type> Node<Type> clone(Node<Type> result)
  540.         {
  541.             if (result != null)
  542.             {
  543.                 result = new Node<>(result.value, clone(result.left), clone(result.right));
  544.             }
  545.             return result;
  546.         }
  547.  
  548.         public static <Type> Node<Type> delete(Node<Type> node, Type value, Comparator<? super Type> comparator)
  549.         {
  550.             Node<Type> result;
  551.             if (node == null)
  552.             {
  553.                 result = null;
  554.             }
  555.             else
  556.             {
  557.                 int compare = comparator.compare(value, node.value);
  558.                 if (compare == 0)
  559.                 {
  560.                     if (node.left == null)
  561.                     {
  562.                         result = node.right;
  563.                     }
  564.                     else
  565.                     {
  566.                         if (node.right == null)
  567.                         {
  568.                             result = node.left;
  569.                         }
  570.                         else
  571.                         {
  572.                             Node<Type> first = first(node.right);
  573.                             result = new Node<>(first.value, node.left, delete(node.right, first.value, comparator));
  574.                         }
  575.                     }
  576.                 }
  577.                 else
  578.                 {
  579.                     if (compare < 0)
  580.                     {
  581.                         result = new Node<>(node.value, delete(node.left, value, comparator), node.right);
  582.                     }
  583.                     else
  584.                     {
  585.                         result = new Node<>(node.value, node.left, delete(node.right, value, comparator));
  586.                     }
  587.                 }
  588.                 result = balance(result);
  589.             }
  590.             return result;
  591.         }
  592.  
  593.         public static <Type> Node<Type> first(Node<Type> result)
  594.         {
  595.             while (result.left != null)
  596.             {
  597.                 result = result.left;
  598.             }
  599.             return result;
  600.         }
  601.  
  602.         public static <Type> Node<Type> get(Node<Type> node, Type value, Comparator<? super Type> comparator)
  603.         {
  604.             Node<Type> result;
  605.             if (node == null)
  606.             {
  607.                 result = null;
  608.             }
  609.             else
  610.             {
  611.                 int compare = comparator.compare(value, node.value);
  612.                 if (compare == 0)
  613.                 {
  614.                     result = node;
  615.                 }
  616.                 else
  617.                 {
  618.                     if (compare < 0)
  619.                     {
  620.                         result = get(node.left, value, comparator);
  621.                     }
  622.                     else
  623.                     {
  624.                         result = get(node.right, value, comparator);
  625.                     }
  626.                 }
  627.             }
  628.             return result;
  629.         }
  630.  
  631.         public static <Type> Node<Type> head(Node<Type> node, Type value, Comparator<? super Type> comparator)
  632.         {
  633.             Node<Type> result;
  634.             if (node == null)
  635.             {
  636.                 result = null;
  637.             }
  638.             else
  639.             {
  640.                 int compare = comparator.compare(value, node.value);
  641.                 if (compare == 0)
  642.                 {
  643.                     result = node.left;
  644.                 }
  645.                 else
  646.                 {
  647.                     if (compare < 0)
  648.                     {
  649.                         result = head(node.left, value, comparator);
  650.                     }
  651.                     else
  652.                     {
  653.                         result = new Node<>(node.value, node.left, head(node.right, value, comparator));
  654.                     }
  655.                 }
  656.                 result = balance(result);
  657.             }
  658.             return result;
  659.         }
  660.  
  661.         public static int height(Node node)
  662.         {
  663.             return node == null ? 0 : node.height;
  664.         }
  665.  
  666.         public static <Type> Node<Type> insert(Node<Type> node, Type value, Comparator<? super Type> comparator)
  667.         {
  668.             Node<Type> result;
  669.             if (node == null)
  670.             {
  671.                 result = new Node<>(value, null, null);
  672.             }
  673.             else
  674.             {
  675.                 int compare = comparator.compare(value, node.value);
  676.                 if (compare == 0)
  677.                 {
  678.                     result = new Node<>(value, node.left, node.right);
  679.                     ;
  680.                 }
  681.                 else
  682.                 {
  683.                     if (compare < 0)
  684.                     {
  685.                         result = new Node<>(node.value, insert(node.left, value, comparator), node.right);
  686.                     }
  687.                     else
  688.                     {
  689.                         result = new Node<>(node.value, node.left, insert(node.right, value, comparator));
  690.                     }
  691.                 }
  692.                 result = balance(result);
  693.             }
  694.             return result;
  695.         }
  696.  
  697.         public static <Type> Node<Type> last(Node<Type> result)
  698.         {
  699.             while (result.right != null)
  700.             {
  701.                 result = result.right;
  702.             }
  703.             return result;
  704.         }
  705.  
  706.         public static int size(Node node)
  707.         {
  708.             return node == null ? 0 : node.size;
  709.         }
  710.  
  711.         public static <Type> Node<Type> tail(Node<Type> node, Type value, Comparator<? super Type> comparator)
  712.         {
  713.             Node<Type> result;
  714.             if (node == null)
  715.             {
  716.                 result = null;
  717.             }
  718.             else
  719.             {
  720.                 int compare = comparator.compare(value, node.value);
  721.                 if (compare == 0)
  722.                 {
  723.                     result = new Node<>(node.value, null, node.right);
  724.                 }
  725.                 else
  726.                 {
  727.                     if (compare < 0)
  728.                     {
  729.                         result = new Node<>(node.value, tail(node.left, value, comparator), node.right);
  730.                     }
  731.                     else
  732.                     {
  733.                         result = tail(node.right, value, comparator);
  734.                     }
  735.                 }
  736.                 result = balance(result);
  737.             }
  738.             return result;
  739.         }
  740.  
  741.         public static <Type> void traverseOrderIn(Node<Type> node, Consumer<Type> consumer)
  742.         {
  743.             if (node != null)
  744.             {
  745.                 traverseOrderIn(node.left, consumer);
  746.                 consumer.accept(node.value);
  747.                 traverseOrderIn(node.right, consumer);
  748.             }
  749.         }
  750.  
  751.         public final Type value;
  752.         public final Node<Type> left;
  753.         public final Node<Type> right;
  754.         public final int size;
  755.         private final int height;
  756.  
  757.         public Node(Type value, Node<Type> left, Node<Type> right)
  758.         {
  759.             this.value = value;
  760.             this.left = left;
  761.             this.right = right;
  762.             this.size = 1 + size(left) + size(right);
  763.             this.height = 1 + Math.max(height(left), height(right));
  764.         }
  765.  
  766.         public Node<Type> rotateLeft()
  767.         {
  768.             Node<Type> left = new Node<>(this.value, this.left, this.right.left);
  769.             return new Node<>(this.right.value, left, this.right.right);
  770.         }
  771.  
  772.         public Node<Type> rotateRight()
  773.         {
  774.             Node<Type> right = new Node<>(this.value, this.left.right, this.right);
  775.             return new Node<>(this.left.value, this.left.left, right);
  776.         }
  777.     }
  778.  
  779.     public static class SortedSetAVL<Type> implements SortedSet<Type>
  780.     {
  781.         public Comparator<? super Type> comparator;
  782.         public Node<Type> root;
  783.  
  784.         private SortedSetAVL(Comparator<? super Type> comparator, Node<Type> root)
  785.         {
  786.             this.comparator = comparator;
  787.             this.root = root;
  788.         }
  789.  
  790.         public SortedSetAVL(Comparator<? super Type> comparator)
  791.         {
  792.             this(comparator, null);
  793.         }
  794.  
  795.         public SortedSetAVL(Collection<? extends Type> collection, Comparator<? super Type> comparator)
  796.         {
  797.             this(comparator, null);
  798.             this.addAll(collection);
  799.         }
  800.  
  801.         public SortedSetAVL(SortedSetAVL<Type> sortedSetAVL)
  802.         {
  803.             this(sortedSetAVL.comparator, Node.clone(sortedSetAVL.root));
  804.         }
  805.  
  806.         @Override
  807.         public void clear()
  808.         {
  809.             this.root = null;
  810.         }
  811.  
  812.         @Override
  813.         public Comparator<? super Type> comparator()
  814.         {
  815.             return this.comparator;
  816.         }
  817.  
  818.         public Type get(Type value)
  819.         {
  820.             Node<Type> node = Node.get(this.root, value, this.comparator);
  821.             return node == null ? null : node.value;
  822.         }
  823.  
  824.         @Override
  825.         public SortedSetAVL<Type> subSet(Type valueStart, Type valueEnd)
  826.         {
  827.             return tailSet(valueStart).headSet(valueEnd);
  828.         }
  829.  
  830.         @Override
  831.         public SortedSetAVL<Type> headSet(Type valueEnd)
  832.         {
  833.             return new SortedSetAVL<>(this.comparator, Node.head(this.root, valueEnd, this.comparator));
  834.         }
  835.  
  836.         @Override
  837.         public SortedSetAVL<Type> tailSet(Type valueStart)
  838.         {
  839.             return new SortedSetAVL<>(this.comparator, Node.tail(this.root, valueStart, this.comparator));
  840.         }
  841.  
  842.         @Override
  843.         public Type first()
  844.         {
  845.             return Node.first(this.root).value;
  846.         }
  847.  
  848.         @Override
  849.         public Type last()
  850.         {
  851.             return Node.last(this.root).value;
  852.         }
  853.  
  854.         @Override
  855.         public int size()
  856.         {
  857.             return this.root == null ? 0 : this.root.size;
  858.         }
  859.  
  860.         @Override
  861.         public boolean isEmpty()
  862.         {
  863.             return this.root == null;
  864.         }
  865.  
  866.         @Override
  867.         public boolean contains(Object value)
  868.         {
  869.             return Node.get(this.root, (Type) value, this.comparator) != null;
  870.         }
  871.  
  872.         @Override
  873.         public Iterator<Type> iterator()
  874.         {
  875.             Stack<Node<Type>> path = new Stack<>();
  876.  
  877.             return new Iterator<Type>()
  878.             {
  879.                 {
  880.                     push(SortedSetAVL.this.root);
  881.                 }
  882.  
  883.                 public void push(Node<Type> node)
  884.                 {
  885.                     while (node != null)
  886.                     {
  887.                         path.push(node);
  888.                         node = node.left;
  889.                     }
  890.                 }
  891.  
  892.                 @Override
  893.                 public boolean hasNext()
  894.                 {
  895.                     return !path.isEmpty();
  896.                 }
  897.  
  898.                 @Override
  899.                 public Type next()
  900.                 {
  901.                     if (path.isEmpty())
  902.                     {
  903.                         throw new NoSuchElementException();
  904.                     }
  905.                     else
  906.                     {
  907.                         Node<Type> node = path.peek();
  908.                         Type result = node.value;
  909.                         if (node.right != null)
  910.                         {
  911.                             push(node.right);
  912.                         }
  913.                         else
  914.                         {
  915.                             do
  916.                             {
  917.                                 node = path.pop();
  918.                             }
  919.                             while (!path.isEmpty() && path.peek().right == node);
  920.                         }
  921.                         return result;
  922.                     }
  923.                 }
  924.             };
  925.         }
  926.  
  927.         @Override
  928.         public Object[] toArray()
  929.         {
  930.             List<Object> list = new ArrayList<>();
  931.             Node.traverseOrderIn(this.root, list::add);
  932.             return list.toArray();
  933.         }
  934.  
  935.         @Override
  936.         public <T> T[] toArray(T[] ts)
  937.         {
  938.             throw new UnsupportedOperationException();
  939.         }
  940.  
  941.         @Override
  942.         public boolean add(Type value)
  943.         {
  944.             int sizeBefore = size();
  945.             this.root = Node.insert(this.root, value, this.comparator);
  946.             return sizeBefore != size();
  947.         }
  948.  
  949.         @Override
  950.         public boolean remove(Object value)
  951.         {
  952.             int sizeBefore = size();
  953.             this.root = Node.delete(this.root, (Type) value, this.comparator);
  954.             return sizeBefore != size();
  955.         }
  956.  
  957.         @Override
  958.         public boolean containsAll(Collection<?> collection)
  959.         {
  960.             return collection.stream()
  961.                     .allMatch(this::contains);
  962.         }
  963.  
  964.         @Override
  965.         public boolean addAll(Collection<? extends Type> collection)
  966.         {
  967.             return collection.stream()
  968.                     .map(this::add)
  969.                     .reduce(true, (x, y) -> x | y);
  970.         }
  971.  
  972.         @Override
  973.         public boolean retainAll(Collection<?> collection)
  974.         {
  975.             SortedSetAVL<Type> set = new SortedSetAVL<>(this.comparator);
  976.             collection.stream()
  977.                     .map(element -> (Type) element)
  978.                     .filter(this::contains)
  979.                     .forEach(set::add);
  980.             boolean result = size() != set.size();
  981.             this.root = set.root;
  982.             return result;
  983.         }
  984.  
  985.         @Override
  986.         public boolean removeAll(Collection<?> collection)
  987.         {
  988.             return collection.stream()
  989.                     .map(this::remove)
  990.                     .reduce(true, (x, y) -> x | y);
  991.         }
  992.  
  993.         @Override
  994.         public String toString()
  995.         {
  996.             return "{" + A_423.toString(this, ", ") + "}";
  997.         }
  998.     }
  999.  
  1000.     public static class SortedMapAVL<TypeKey, TypeValue> implements SortedMap<TypeKey, TypeValue>
  1001.     {
  1002.         public final Comparator<? super TypeKey> comparator;
  1003.         public final SortedSetAVL<Entry<TypeKey, TypeValue>> entrySet;
  1004.  
  1005.         public SortedMapAVL(Comparator<? super TypeKey> comparator)
  1006.         {
  1007.             this(comparator, new SortedSetAVL<>((entry0, entry1) -> comparator.compare(entry0.getKey(), entry1.getKey())));
  1008.         }
  1009.  
  1010.         private SortedMapAVL(Comparator<? super TypeKey> comparator, SortedSetAVL<Entry<TypeKey, TypeValue>> entrySet)
  1011.         {
  1012.             this.comparator = comparator;
  1013.             this.entrySet = entrySet;
  1014.         }
  1015.  
  1016.         @Override
  1017.         public Comparator<? super TypeKey> comparator()
  1018.         {
  1019.             return this.comparator;
  1020.         }
  1021.  
  1022.         @Override
  1023.         public SortedMapAVL<TypeKey, TypeValue> subMap(TypeKey keyStart, TypeKey keyEnd)
  1024.         {
  1025.             return new SortedMapAVL<>(this.comparator, this.entrySet.subSet(new AbstractMap.SimpleEntry<>(keyStart, null), new AbstractMap.SimpleEntry<>(keyEnd, null)));
  1026.         }
  1027.  
  1028.         @Override
  1029.         public SortedMapAVL<TypeKey, TypeValue> headMap(TypeKey keyEnd)
  1030.         {
  1031.             return new SortedMapAVL<>(this.comparator, this.entrySet.headSet(new AbstractMap.SimpleEntry<>(keyEnd, null)));
  1032.         }
  1033.  
  1034.         @Override
  1035.         public SortedMapAVL<TypeKey, TypeValue> tailMap(TypeKey keyStart)
  1036.         {
  1037.             return new SortedMapAVL<>(this.comparator, this.entrySet.tailSet(new AbstractMap.SimpleEntry<>(keyStart, null)));
  1038.         }
  1039.  
  1040.         public Entry<TypeKey, TypeValue> firstEntry()
  1041.         {
  1042.             return this.entrySet.first();
  1043.         }
  1044.  
  1045.         @Override
  1046.         public TypeKey firstKey()
  1047.         {
  1048.             return firstEntry().getKey();
  1049.         }
  1050.  
  1051.         public Entry<TypeKey, TypeValue> lastEntry()
  1052.         {
  1053.             return this.entrySet.last();
  1054.         }
  1055.  
  1056.         @Override
  1057.         public TypeKey lastKey()
  1058.         {
  1059.             return lastEntry().getKey();
  1060.         }
  1061.  
  1062.         @Override
  1063.         public int size()
  1064.         {
  1065.             return this.entrySet().size();
  1066.         }
  1067.  
  1068.         @Override
  1069.         public boolean isEmpty()
  1070.         {
  1071.             return this.entrySet.isEmpty();
  1072.         }
  1073.  
  1074.         @Override
  1075.         public boolean containsKey(Object key)
  1076.         {
  1077.             return this.entrySet().contains(new AbstractMap.SimpleEntry<>((TypeKey) key, null));
  1078.         }
  1079.  
  1080.         @Override
  1081.         public boolean containsValue(Object value)
  1082.         {
  1083.             throw new UnsupportedOperationException();
  1084.         }
  1085.  
  1086.         @Override
  1087.         public TypeValue get(Object key)
  1088.         {
  1089.             Entry<TypeKey, TypeValue> entry = new AbstractMap.SimpleEntry<>((TypeKey) key, null);
  1090.             entry = this.entrySet.get(entry);
  1091.             return entry == null ? null : entry.getValue();
  1092.         }
  1093.  
  1094.         @Override
  1095.         public TypeValue put(TypeKey key, TypeValue value)
  1096.         {
  1097.             TypeValue result = get(key);
  1098.             Entry<TypeKey, TypeValue> entry = new AbstractMap.SimpleEntry<>(key, value);
  1099.             this.entrySet().add(entry);
  1100.             return result;
  1101.         }
  1102.  
  1103.         @Override
  1104.         public TypeValue remove(Object key)
  1105.         {
  1106.             TypeValue result = get(key);
  1107.             Entry<TypeKey, TypeValue> entry = new AbstractMap.SimpleEntry<>((TypeKey) key, null);
  1108.             this.entrySet.remove(entry);
  1109.             return result;
  1110.         }
  1111.  
  1112.         @Override
  1113.         public void putAll(Map<? extends TypeKey, ? extends TypeValue> map)
  1114.         {
  1115.             map.entrySet()
  1116.                     .forEach(entry -> put(entry.getKey(), entry.getValue()));
  1117.         }
  1118.  
  1119.         @Override
  1120.         public void clear()
  1121.         {
  1122.             this.entrySet.clear();
  1123.         }
  1124.  
  1125.         @Override
  1126.         public Set<TypeKey> keySet()
  1127.         {
  1128.             throw new UnsupportedOperationException();
  1129.         }
  1130.  
  1131.         @Override
  1132.         public Collection<TypeValue> values()
  1133.         {
  1134.             return new Collection<TypeValue>()
  1135.             {
  1136.                 @Override
  1137.                 public int size()
  1138.                 {
  1139.                     return SortedMapAVL.this.entrySet.size();
  1140.                 }
  1141.  
  1142.                 @Override
  1143.                 public boolean isEmpty()
  1144.                 {
  1145.                     return SortedMapAVL.this.entrySet.isEmpty();
  1146.                 }
  1147.  
  1148.                 @Override
  1149.                 public boolean contains(Object value)
  1150.                 {
  1151.                     throw new UnsupportedOperationException();
  1152.                 }
  1153.  
  1154.                 @Override
  1155.                 public Iterator<TypeValue> iterator()
  1156.                 {
  1157.                     return new Iterator<TypeValue>()
  1158.                     {
  1159.                         Iterator<Entry<TypeKey, TypeValue>> iterator = SortedMapAVL.this.entrySet.iterator();
  1160.  
  1161.                         @Override
  1162.                         public boolean hasNext()
  1163.                         {
  1164.                             return this.iterator.hasNext();
  1165.                         }
  1166.  
  1167.                         @Override
  1168.                         public TypeValue next()
  1169.                         {
  1170.                             return this.iterator.next().getValue();
  1171.                         }
  1172.                     };
  1173.                 }
  1174.  
  1175.                 @Override
  1176.                 public Object[] toArray()
  1177.                 {
  1178.                     throw new UnsupportedOperationException();
  1179.                 }
  1180.  
  1181.                 @Override
  1182.                 public <T> T[] toArray(T[] ts)
  1183.                 {
  1184.                     throw new UnsupportedOperationException();
  1185.                 }
  1186.  
  1187.                 @Override
  1188.                 public boolean add(TypeValue typeValue)
  1189.                 {
  1190.                     throw new UnsupportedOperationException();
  1191.                 }
  1192.  
  1193.                 @Override
  1194.                 public boolean remove(Object o)
  1195.                 {
  1196.                     throw new UnsupportedOperationException();
  1197.                 }
  1198.  
  1199.                 @Override
  1200.                 public boolean containsAll(Collection<?> collection)
  1201.                 {
  1202.                     throw new UnsupportedOperationException();
  1203.                 }
  1204.  
  1205.                 @Override
  1206.                 public boolean addAll(Collection<? extends TypeValue> collection)
  1207.                 {
  1208.                     throw new UnsupportedOperationException();
  1209.                 }
  1210.  
  1211.                 @Override
  1212.                 public boolean removeAll(Collection<?> collection)
  1213.                 {
  1214.                     throw new UnsupportedOperationException();
  1215.                 }
  1216.  
  1217.                 @Override
  1218.                 public boolean retainAll(Collection<?> collection)
  1219.                 {
  1220.                     throw new UnsupportedOperationException();
  1221.                 }
  1222.  
  1223.                 @Override
  1224.                 public void clear()
  1225.                 {
  1226.                     throw new UnsupportedOperationException();
  1227.                 }
  1228.             };
  1229.         }
  1230.  
  1231.         @Override
  1232.         public SortedSetAVL<Entry<TypeKey, TypeValue>> entrySet()
  1233.         {
  1234.             return this.entrySet;
  1235.         }
  1236.  
  1237.         @Override
  1238.         public String toString()
  1239.         {
  1240.             return this.entrySet().toString();
  1241.         }
  1242.     }
  1243.  
  1244.     public static class FIFO<Type>
  1245.     {
  1246.         public SingleLinkedList<Type> start;
  1247.         public SingleLinkedList<Type> end;
  1248.  
  1249.         public FIFO()
  1250.         {
  1251.             this.start = null;
  1252.             this.end = null;
  1253.         }
  1254.  
  1255.         public boolean isEmpty()
  1256.         {
  1257.             return this.start == null;
  1258.         }
  1259.  
  1260.         public Type peek()
  1261.         {
  1262.             return this.start.element;
  1263.         }
  1264.  
  1265.         public Type pop()
  1266.         {
  1267.             Type result = this.start.element;
  1268.             this.start = this.start.next;
  1269.             return result;
  1270.         }
  1271.  
  1272.         public void push(Type element)
  1273.         {
  1274.             SingleLinkedList<Type> list = new SingleLinkedList<>(element, null);
  1275.             if (this.start == null)
  1276.             {
  1277.                 this.start = list;
  1278.                 this.end = list;
  1279.             }
  1280.             else
  1281.             {
  1282.                 this.end.next = list;
  1283.                 this.end = list;
  1284.             }
  1285.         }
  1286.     }
  1287.  
  1288.     public static class MapCount<Type> extends SortedMapAVL<Type, Long>
  1289.     {
  1290.         private int count;
  1291.  
  1292.         public MapCount(Comparator<? super Type> comparator)
  1293.         {
  1294.             super(comparator);
  1295.             this.count = 0;
  1296.         }
  1297.  
  1298.         public long add(Type key, Long delta)
  1299.         {
  1300.             long result;
  1301.             if (delta > 0)
  1302.             {
  1303.                 Long value = get(key);
  1304.                 if (value == null)
  1305.                 {
  1306.                     value = delta;
  1307.                 }
  1308.                 else
  1309.                 {
  1310.                     value += delta;
  1311.                 }
  1312.                 put(key, value);
  1313.                 result = delta;
  1314.             }
  1315.             else
  1316.             {
  1317.                 result = 0;
  1318.             }
  1319.             this.count += result;
  1320.             return result;
  1321.         }
  1322.  
  1323.         public int count()
  1324.         {
  1325.             return this.count;
  1326.         }
  1327.  
  1328.         public List<Type> flatten()
  1329.         {
  1330.             List<Type> result = new ArrayList<>();
  1331.             for (Entry<Type, Long> entry : entrySet())
  1332.             {
  1333.                 for (long index = 0; index < entry.getValue(); index++)
  1334.                 {
  1335.                     result.add(entry.getKey());
  1336.                 }
  1337.             }
  1338.             return result;
  1339.         }
  1340.  
  1341.         @Override
  1342.         public void putAll(Map<? extends Type, ? extends Long> map)
  1343.         {
  1344.             throw new UnsupportedOperationException();
  1345.         }
  1346.  
  1347.         @Override
  1348.         public Long remove(Object key)
  1349.         {
  1350.             Long result = super.remove(key);
  1351.             this.count -= result;
  1352.             return result;
  1353.         }
  1354.  
  1355.         public long remove(Type key, Long delta)
  1356.         {
  1357.             long result;
  1358.             if (delta > 0)
  1359.             {
  1360.                 Long value = get(key) - delta;
  1361.                 if (value <= 0)
  1362.                 {
  1363.                     result = delta + value;
  1364.                     remove(key);
  1365.                 }
  1366.                 else
  1367.                 {
  1368.                     result = delta;
  1369.                     put(key, value);
  1370.                 }
  1371.             }
  1372.             else
  1373.             {
  1374.                 result = 0;
  1375.             }
  1376.             this.count -= result;
  1377.             return result;
  1378.         }
  1379.  
  1380.         @Override
  1381.         public SortedMapAVL<Type, Long> subMap(Type keyStart, Type keyEnd)
  1382.         {
  1383.             throw new UnsupportedOperationException();
  1384.         }
  1385.  
  1386.         @Override
  1387.         public SortedMapAVL<Type, Long> headMap(Type keyEnd)
  1388.         {
  1389.             throw new UnsupportedOperationException();
  1390.         }
  1391.  
  1392.         @Override
  1393.         public SortedMapAVL<Type, Long> tailMap(Type keyStart)
  1394.         {
  1395.             throw new UnsupportedOperationException();
  1396.         }
  1397.     }
  1398.  
  1399.     public static class MapSet<TypeKey, TypeValue> extends SortedMapAVL<TypeKey, SortedSetAVL<TypeValue>> implements Iterable<TypeValue>
  1400.     {
  1401.         private Comparator<? super TypeValue> comparatorValue;
  1402.  
  1403.         public MapSet(Comparator<? super TypeKey> comparatorKey, Comparator<? super TypeValue> comparatorValue)
  1404.         {
  1405.             super(comparatorKey);
  1406.             this.comparatorValue = comparatorValue;
  1407.         }
  1408.  
  1409.         public MapSet(Comparator<? super TypeKey> comparatorKey, SortedSetAVL<Entry<TypeKey, SortedSetAVL<TypeValue>>> entrySet, Comparator<? super TypeValue> comparatorValue)
  1410.         {
  1411.             super(comparatorKey, entrySet);
  1412.             this.comparatorValue = comparatorValue;
  1413.         }
  1414.  
  1415.         public TypeValue firstValue()
  1416.         {
  1417.             TypeValue result;
  1418.             Entry<TypeKey, SortedSetAVL<TypeValue>> firstEntry = firstEntry();
  1419.             if (firstEntry == null)
  1420.             {
  1421.                 result = null;
  1422.             }
  1423.             else
  1424.             {
  1425.                 result = firstEntry.getValue().first();
  1426.             }
  1427.             return result;
  1428.         }
  1429.  
  1430.         public Iterator<TypeValue> iterator()
  1431.         {
  1432.             return new Iterator<TypeValue>()
  1433.             {
  1434.                 Iterator<SortedSetAVL<TypeValue>> iteratorValues = values().iterator();
  1435.                 Iterator<TypeValue> iteratorValue = null;
  1436.  
  1437.                 @Override
  1438.                 public boolean hasNext()
  1439.                 {
  1440.                     return iteratorValues.hasNext() || (iteratorValue != null && iteratorValue.hasNext());
  1441.                 }
  1442.  
  1443.                 @Override
  1444.                 public TypeValue next()
  1445.                 {
  1446.                     if (iteratorValue == null || !iteratorValue.hasNext())
  1447.                     {
  1448.                         iteratorValue = iteratorValues.next().iterator();
  1449.                     }
  1450.                     return iteratorValue.next();
  1451.                 }
  1452.             };
  1453.         }
  1454.  
  1455.         public TypeValue lastValue()
  1456.         {
  1457.             TypeValue result;
  1458.             Entry<TypeKey, SortedSetAVL<TypeValue>> lastEntry = lastEntry();
  1459.             if (lastEntry == null)
  1460.             {
  1461.                 result = null;
  1462.             }
  1463.             else
  1464.             {
  1465.                 result = lastEntry.getValue().last();
  1466.             }
  1467.             return result;
  1468.         }
  1469.  
  1470.         public boolean add(TypeKey key, TypeValue value)
  1471.         {
  1472.             SortedSetAVL<TypeValue> set = computeIfAbsent(key, k -> new SortedSetAVL<>(comparatorValue));
  1473.             return set.add(value);
  1474.         }
  1475.  
  1476.         public boolean removeSet(TypeKey key, TypeValue value)
  1477.         {
  1478.             boolean result;
  1479.             SortedSetAVL<TypeValue> set = get(key);
  1480.             if (set == null)
  1481.             {
  1482.                 result = false;
  1483.             }
  1484.             else
  1485.             {
  1486.                 result = set.remove(value);
  1487.                 if (set.size() == 0)
  1488.                 {
  1489.                     remove(key);
  1490.                 }
  1491.             }
  1492.             return result;
  1493.         }
  1494.  
  1495.         @Override
  1496.         public MapSet<TypeKey, TypeValue> headMap(TypeKey keyEnd)
  1497.         {
  1498.             return new MapSet<>(this.comparator, this.entrySet.headSet(new AbstractMap.SimpleEntry<>(keyEnd, null)), this.comparatorValue);
  1499.         }
  1500.  
  1501.         @Override
  1502.         public MapSet<TypeKey, TypeValue> tailMap(TypeKey keyStart)
  1503.         {
  1504.             return new MapSet<>(this.comparator, this.entrySet.tailSet(new AbstractMap.SimpleEntry<>(keyStart, null)), this.comparatorValue);
  1505.         }
  1506.     }
  1507.  
  1508.     static class IteratorBuffer<Type>
  1509.     {
  1510.         private Iterator<Type> iterator;
  1511.         private List<Type> list;
  1512.  
  1513.         public IteratorBuffer(Iterator<Type> iterator)
  1514.         {
  1515.             this.iterator = iterator;
  1516.             this.list = new ArrayList<Type>();
  1517.         }
  1518.  
  1519.         public Iterator<Type> iterator()
  1520.         {
  1521.             return new Iterator<Type>()
  1522.             {
  1523.                 int index = 0;
  1524.  
  1525.                 @Override
  1526.                 public boolean hasNext()
  1527.                 {
  1528.                     return this.index < list.size() || iterator().hasNext();
  1529.                 }
  1530.  
  1531.                 @Override
  1532.                 public Type next()
  1533.                 {
  1534.                     if (list.size() <= this.index)
  1535.                     {
  1536.                         list.add(iterator.next());
  1537.                     }
  1538.                     Type result = list.get(index);
  1539.                     index += 1;
  1540.                     return result;
  1541.                 }
  1542.             };
  1543.         }
  1544.     }
  1545.  
  1546.     public static <Type> List<List<Type>> permutations(List<Type> list)
  1547.     {
  1548.         List<List<Type>> result = new ArrayList<>();
  1549.         result.add(new ArrayList<>());
  1550.         for (Type element : list)
  1551.         {
  1552.             List<List<Type>> permutations = result;
  1553.             result = new ArrayList<>();
  1554.             for (List<Type> permutation : permutations)
  1555.             {
  1556.                 for (int index = 0; index <= permutation.size(); index++)
  1557.                 {
  1558.                     List<Type> permutationNew = new ArrayList<>(permutation);
  1559.                     permutationNew.add(index, element);
  1560.                     result.add(permutationNew);
  1561.                 }
  1562.             }
  1563.         }
  1564.         return result;
  1565.     }
  1566.  
  1567.     public static List<List<Integer>> combinations(int n, int k)
  1568.     {
  1569.         List<List<Integer>> result = new ArrayList<>();
  1570.         if (k == 0)
  1571.         {
  1572.         }
  1573.         else
  1574.         {
  1575.             if (k == 1)
  1576.             {
  1577.                 List<Integer> combination = new ArrayList<>();
  1578.                 combination.add(n);
  1579.                 result.add(combination);
  1580.             }
  1581.             else
  1582.             {
  1583.                 for (int index = 0; index <= n; index++)
  1584.                 {
  1585.                     for (List<Integer> combination : combinations(n - index, k - 1))
  1586.                     {
  1587.                         combination.add(index);
  1588.                         result.add(combination);
  1589.                     }
  1590.                 }
  1591.             }
  1592.         }
  1593.         return result;
  1594.     }
  1595.  
  1596.     public static <Type> int compare(Iterator<Type> iterator0, Iterator<Type> iterator1, Comparator<Type> comparator)
  1597.     {
  1598.         int result = 0;
  1599.         while (result == 0 && iterator0.hasNext() && iterator1.hasNext())
  1600.         {
  1601.             result = comparator.compare(iterator0.next(), iterator1.next());
  1602.         }
  1603.         if (result == 0)
  1604.         {
  1605.             if (iterator1.hasNext())
  1606.             {
  1607.                 result = -1;
  1608.             }
  1609.             else
  1610.             {
  1611.                 if (iterator0.hasNext())
  1612.                 {
  1613.                     result = 1;
  1614.                 }
  1615.             }
  1616.         }
  1617.         return result;
  1618.     }
  1619.  
  1620.     public static <Type> int compare(Iterable<Type> iterable0, Iterable<Type> iterable1, Comparator<Type> comparator)
  1621.     {
  1622.         return compare(iterable0.iterator(), iterable1.iterator(), comparator);
  1623.     }
  1624.  
  1625.     private static String nextString() throws IOException
  1626.     {
  1627.         while ((stringTokenizer == null) || (!stringTokenizer.hasMoreTokens()))
  1628.         {
  1629.             stringTokenizer = new StringTokenizer(bufferedReader.readLine());
  1630.         }
  1631.         return stringTokenizer.nextToken();
  1632.     }
  1633.  
  1634.     private static String[] nextStrings(int n) throws IOException
  1635.     {
  1636.         String[] result = new String[n];
  1637.         {
  1638.             for (int index = 0; index < n; index++)
  1639.             {
  1640.                 result[index] = nextString();
  1641.             }
  1642.         }
  1643.         return result;
  1644.     }
  1645.  
  1646.     public static int nextInt() throws IOException
  1647.     {
  1648.         return Integer.parseInt(nextString());
  1649.     }
  1650.  
  1651.     public static int[] nextInts(int n) throws IOException
  1652.     {
  1653.         int[] result = new int[n];
  1654.         {
  1655.             for (int index = 0; index < n; index++)
  1656.             {
  1657.                 result[index] = nextInt();
  1658.             }
  1659.         }
  1660.         return result;
  1661.     }
  1662.  
  1663.     public static double nextDouble() throws IOException
  1664.     {
  1665.         return Double.parseDouble(nextString());
  1666.     }
  1667.  
  1668.     public static long nextLong() throws IOException
  1669.     {
  1670.         return Long.parseLong(nextString());
  1671.     }
  1672.  
  1673.     public static long[] nextLongs(int n) throws IOException
  1674.     {
  1675.         long[] result = new long[n];
  1676.         {
  1677.             for (int index = 0; index < n; index++)
  1678.             {
  1679.                 result[index] = nextLong();
  1680.             }
  1681.         }
  1682.         return result;
  1683.     }
  1684.  
  1685.     public static String nextLine() throws IOException
  1686.     {
  1687.         return bufferedReader.readLine();
  1688.     }
  1689.  
  1690.     public static void close()
  1691.     {
  1692.         out.close();
  1693.     }
  1694.  
  1695.     public static int binarySearchMinimum(Function<Integer, Boolean> filter, int start, int end)
  1696.     {
  1697.         int result;
  1698.         if (start == end)
  1699.         {
  1700.             result = end;
  1701.         }
  1702.         else
  1703.         {
  1704.             int middle = start + (end - start) / 2;
  1705.             if (filter.apply(middle))
  1706.             {
  1707.                 result = binarySearchMinimum(filter, start, middle);
  1708.             }
  1709.             else
  1710.             {
  1711.                 result = binarySearchMinimum(filter, middle + 1, end);
  1712.             }
  1713.         }
  1714.         return result;
  1715.     }
  1716.  
  1717.     public static int binarySearchMaximum(Function<Integer, Boolean> filter, int start, int end)
  1718.     {
  1719.         return -binarySearchMinimum(x -> filter.apply(-x), -end, -start);
  1720.     }
  1721.  
  1722.     public static long divideCeil(long x, long y)
  1723.     {
  1724.         return (x + y - 1) / y;
  1725.     }
  1726.  
  1727.     public static Set<Long> divisors(long n)
  1728.     {
  1729.         SortedSetAVL<Long> result = new SortedSetAVL<>(Comparator.naturalOrder());
  1730.         result.add(1L);
  1731.         for (Long factor : factors(n))
  1732.         {
  1733.             SortedSetAVL<Long> divisors = new SortedSetAVL<>(result);
  1734.             for (Long divisor : result)
  1735.             {
  1736.                 divisors.add(divisor * factor);
  1737.             }
  1738.             result = divisors;
  1739.         }
  1740.         return result;
  1741.     }
  1742.  
  1743.     public static long faculty(int n)
  1744.     {
  1745.         long result = 1;
  1746.         for (int index = 2; index <= n; index++)
  1747.         {
  1748.             result *= index;
  1749.         }
  1750.         return result;
  1751.     }
  1752.  
  1753.     public static LinkedList<Long> factors(long n)
  1754.     {
  1755.         LinkedList<Long> result = new LinkedList<>();
  1756.         Iterator<Long> primes = ITERATOR_BUFFER_PRIME.iterator();
  1757.         Long prime;
  1758.         while (n > 1 && (prime = primes.next()) * prime <= n)
  1759.         {
  1760.             while (n % prime == 0)
  1761.             {
  1762.                 result.add(prime);
  1763.                 n /= prime;
  1764.             }
  1765.         }
  1766.         if (n > 1)
  1767.         {
  1768.             result.add(n);
  1769.         }
  1770.         return result;
  1771.     }
  1772.  
  1773.     public static long gcd(long a, long b)
  1774.     {
  1775.         while (a != 0 && b != 0)
  1776.         {
  1777.             if (a > b)
  1778.             {
  1779.                 a %= b;
  1780.             }
  1781.             else
  1782.             {
  1783.                 b %= a;
  1784.             }
  1785.         }
  1786.         return a + b;
  1787.     }
  1788.  
  1789.     public static long[] generatePOWER2()
  1790.     {
  1791.         long[] result = new long[63];
  1792.         for (int x = 0; x < result.length; x++)
  1793.         {
  1794.             result[x] = 1L << x;
  1795.         }
  1796.         return result;
  1797.     }
  1798.  
  1799.     public static boolean isPrime(long x)
  1800.     {
  1801.         boolean result = x > 1;
  1802.         Iterator<Long> iterator = ITERATOR_BUFFER_PRIME.iterator();
  1803.         Long prime;
  1804.         while ((prime = iterator.next()) * prime <= x)
  1805.         {
  1806.             result &= x % prime > 0;
  1807.         }
  1808.         return result;
  1809.     }
  1810.  
  1811.     public static long knapsack(List<Tuple3<Long, Integer, Integer>> itemsValueWeightCount, int weightMaximum)
  1812.     {
  1813.         long[] valuesMaximum = new long[weightMaximum + 1];
  1814.         for (Tuple3<Long, Integer, Integer> itemValueWeightCount : itemsValueWeightCount)
  1815.         {
  1816.             long itemValue = itemValueWeightCount.v0;
  1817.             int itemWeight = itemValueWeightCount.v1;
  1818.             int itemCount = itemValueWeightCount.v2;
  1819.             for (int weight = weightMaximum; 0 <= weight; weight--)
  1820.             {
  1821.                 for (int index = 1; index <= itemCount && 0 <= weight - index * itemWeight; index++)
  1822.                 {
  1823.                     valuesMaximum[weight] = Math.max(valuesMaximum[weight], valuesMaximum[weight - index * itemWeight] + index * itemValue);
  1824.                 }
  1825.             }
  1826.         }
  1827.         long result = 0;
  1828.         for (long valueMaximum : valuesMaximum)
  1829.         {
  1830.             result = Math.max(result, valueMaximum);
  1831.         }
  1832.         return result;
  1833.     }
  1834.  
  1835.     public static boolean knapsackPossible(List<Tuple2<Integer, Integer>> itemsWeightCount, int weightMaximum)
  1836.     {
  1837.         boolean[] weightPossible = new boolean[weightMaximum + 1];
  1838.         weightPossible[0] = true;
  1839.         int weightLargest = 0;
  1840.         for (Tuple2<Integer, Integer> itemWeightCount : itemsWeightCount)
  1841.         {
  1842.             int itemWeight = itemWeightCount.v0;
  1843.             int itemCount = itemWeightCount.v1;
  1844.             for (int weightStart = 0; weightStart < itemWeight; weightStart++)
  1845.             {
  1846.                 int count = 0;
  1847.                 for (int weight = weightStart; weight <= weightMaximum && (0 < count || weight <= weightLargest); weight += itemWeight)
  1848.                 {
  1849.                     if (weightPossible[weight])
  1850.                     {
  1851.                         count = itemCount;
  1852.                     }
  1853.                     else
  1854.                     {
  1855.                         if (0 < count)
  1856.                         {
  1857.                             weightPossible[weight] = true;
  1858.                             weightLargest = weight;
  1859.                             count -= 1;
  1860.                         }
  1861.                     }
  1862.                 }
  1863.             }
  1864.         }
  1865.         return weightPossible[weightMaximum];
  1866.     }
  1867.  
  1868.     public static long lcm(int a, int b)
  1869.     {
  1870.         return a * b / gcd(a, b);
  1871.     }
  1872.  
  1873.     public static <T> List<T> permutation(long p, List<T> x)
  1874.     {
  1875.         List<T> copy = new ArrayList<>();
  1876.         for (int index = 0; index < x.size(); index++)
  1877.         {
  1878.             copy.add(x.get(index));
  1879.         }
  1880.         List<T> result = new ArrayList<>();
  1881.         for (int indexTo = 0; indexTo < x.size(); indexTo++)
  1882.         {
  1883.             int indexFrom = (int) p % copy.size();
  1884.             p = p / copy.size();
  1885.             result.add(copy.remove(indexFrom));
  1886.         }
  1887.         return result;
  1888.     }
  1889.  
  1890.     public static <Type> String toString(Iterator<Type> iterator, String separator)
  1891.     {
  1892.         StringBuilder stringBuilder = new StringBuilder();
  1893.         if (iterator.hasNext())
  1894.         {
  1895.             stringBuilder.append(iterator.next());
  1896.         }
  1897.         while (iterator.hasNext())
  1898.         {
  1899.             stringBuilder.append(separator);
  1900.             stringBuilder.append(iterator.next());
  1901.         }
  1902.         return stringBuilder.toString();
  1903.     }
  1904.  
  1905.     public static <Type> String toString(Iterator<Type> iterator)
  1906.     {
  1907.         return toString(iterator, " ");
  1908.     }
  1909.  
  1910.     public static <Type> String toString(Iterable<Type> iterable, String separator)
  1911.     {
  1912.         return toString(iterable.iterator(), separator);
  1913.     }
  1914.  
  1915.     public static <Type> String toString(Iterable<Type> iterable)
  1916.     {
  1917.         return toString(iterable, " ");
  1918.     }
  1919.  
  1920.     public static Stream<BigInteger> streamFibonacci()
  1921.     {
  1922.         return Stream.generate(new Supplier<BigInteger>()
  1923.         {
  1924.             private BigInteger n0 = BigInteger.ZERO;
  1925.             private BigInteger n1 = BigInteger.ONE;
  1926.  
  1927.             @Override
  1928.             public BigInteger get()
  1929.             {
  1930.                 BigInteger result = n0;
  1931.                 n0 = n1;
  1932.                 n1 = result.add(n0);
  1933.                 return result;
  1934.             }
  1935.         });
  1936.     }
  1937.  
  1938.     public static Stream<Long> streamPrime(int sieveSize)
  1939.     {
  1940.         return Stream.generate(new Supplier<Long>()
  1941.         {
  1942.             private boolean[] isPrime = new boolean[sieveSize];
  1943.             private long sieveOffset = 2;
  1944.             private List<Long> primes = new ArrayList<>();
  1945.             private int index = 0;
  1946.  
  1947.             public void filter(long prime, boolean[] result)
  1948.             {
  1949.                 if (prime * prime < this.sieveOffset + sieveSize)
  1950.                 {
  1951.                     long remainingStart = this.sieveOffset % prime;
  1952.                     long start = remainingStart == 0 ? 0 : prime - remainingStart;
  1953.                     for (long index = start; index < sieveSize; index += prime)
  1954.                     {
  1955.                         result[(int) index] = false;
  1956.                     }
  1957.                 }
  1958.             }
  1959.  
  1960.             public void generatePrimes()
  1961.             {
  1962.                 Arrays.fill(this.isPrime, true);
  1963.                 this.primes.forEach(prime -> filter(prime, isPrime));
  1964.                 for (int index = 0; index < sieveSize; index++)
  1965.                 {
  1966.                     if (isPrime[index])
  1967.                     {
  1968.                         this.primes.add(this.sieveOffset + index);
  1969.                         filter(this.sieveOffset + index, isPrime);
  1970.                     }
  1971.                 }
  1972.                 this.sieveOffset += sieveSize;
  1973.             }
  1974.  
  1975.             @Override
  1976.             public Long get()
  1977.             {
  1978.                 while (this.primes.size() <= this.index)
  1979.                 {
  1980.                     generatePrimes();
  1981.                 }
  1982.                 Long result = this.primes.get(this.index);
  1983.                 this.index += 1;
  1984.                 return result;
  1985.             }
  1986.         });
  1987.     }
  1988.  
  1989.     public static long totient(long n)
  1990.     {
  1991.         Set<Long> factors = new SortedSetAVL<>(factors(n), Comparator.naturalOrder());
  1992.         long result = n;
  1993.         for (long p : factors)
  1994.         {
  1995.             result -= result / p;
  1996.         }
  1997.         return result;
  1998.     }
  1999.  
  2000.     public static void main(String[] args)
  2001.     {
  2002.         try
  2003.         {
  2004.             solve();
  2005.         } catch (IOException exception)
  2006.         {
  2007.             exception.printStackTrace();
  2008.         }
  2009.         close();
  2010.     }
  2011.  
  2012.     public static void solve() throws IOException
  2013.     {
  2014.         int a = 1;
  2015.     }
  2016. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top