CodeForcesTemplate.md
```cs
using System;
using System.IO;
using System.Collections.Generic;
using System.Numerics;
using System.Text;
using System.Linq;
using System.Buffers;
using System.Globalization;
namespace TestingStuff;
#region Вспомогательные штуки
public class CustomComparer : IComparer
{
private Func compareFunc;
public CustomComparer(Func compareFunc) =>
this.compareFunc = compareFunc;
public int Compare(T? x, T? y) =>
compareFunc(x, y);
}
#endregion
#region Все мейн методы
public static class Extensions
{
public static long CeliDiv(this long a, long b)
{
return (a + b - 1) / b;
}
public static ulong CeliDiv(this ulong a, ulong b)
{
return (a + b - 1) / b;
}
public static long Gcd(this long a, long b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
public static ulong Gcd(this ulong a, ulong b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
return a | b;
}
public static long Lcm(this long a, long b)
{
return a / Gcd(a, b) * b;
}
public static ulong Lcm(this ulong a, ulong b)
{
return a / Gcd(a, b) * b;
}
public static long BinPow(this long x, long pow)
{
long ret = 1;
pow = Math.Abs(pow);
while (pow != 0)
{
if ((pow & 1) == 1)
ret *= x;
x *= x;
pow >>= 1;
}
return ret;
}
public static long BinPow(this long x, long pow, long mod)
{
long ret = 1;
x %= mod;
pow = Math.Abs(pow);
while (pow != 0)
{
if ((pow & 1) == 1)
{
ret *= x;
ret %= mod;
}
x *= x;
x %= mod;
pow >>= 1;
}
return ret;
}
public static ulong ActualBitsNOT(this ulong number)
{
if (number == 0 || BitOperations.IsPow2(number))
{
return number - 1;
}
else
{
ulong mask = BitOperations.RoundUpToPowerOf2(number) - 1;
return ~number & mask;
}
}
public static ulong GetMaxBit(this ulong number)
{
if (number == 0)
return 0;
return 1UL << BitOperations.Log2(number);
}
public static (T, int, T, int) MinIndexMaxIndex(this Span arr)
where T : IComparable
{
int minIndex = 0, maxIndex = 0;
for (int i = 1; i < arr.Length; i++)
{
if (arr[i].CompareTo(arr[minIndex]) < 0)
minIndex = i;
if (arr[i].CompareTo(arr[maxIndex]) > 0)
maxIndex = i;
}
return (arr[minIndex], minIndex, arr[maxIndex], maxIndex);
}
public static int LowerBoundIndex(this Span arr, T value)
where T : IComparable
{
int left = -1, right = arr.Length;
while (right - left > 1)
{
int mid = (left + right) >> 1;
if (arr[mid].CompareTo(value) < 0)
left = mid;
else
right = mid;
}
return right;
}
public static int UpperBoundIndex(this Span arr, T value)
where T : IComparable
{
int left = -1, right = arr.Length;
while (right - left > 1)
{
int mid = (left + right) >> 1;
if (arr[mid].CompareTo(value) <= 0)
left = mid;
else
right = mid;
}
return right;
}
public static Span GenericPrefixSum(this Span arr, T zero, Func operation)
{
Span newArr = new T[arr.Length + 1];
newArr[0] = zero;
for (int i = 0; i < arr.Length; i++)
{
newArr[i + 1] = operation(newArr[i], arr[i]);
}
return newArr;
}
public static TV GetOrAdd(this IDictionary dictionary, TK key, TV value)
{
if (dictionary.TryGetValue(key, out TV? tempVal))
{
return tempVal;
}
dictionary.Add(key, value);
return value;
}
public static TV GetOrAdd(this IDictionary dictionary, TK key, Func valueFactory)
{
if (dictionary.TryGetValue(key, out TV? tempVal))
{
return tempVal;
}
dictionary.Add(key, valueFactory());
return dictionary[key];
}
public static void FromSpan(this ICollection collection, Span span)
{
for (int i = 0; i < span.Length; i++)
{
collection.Add(span[i]);
}
}
}
#endregion
public class Program
{
#region Пресеты
public static void Swap(ref T left, ref T right)
{
(right, left) = (left, right);
}
public static Span InputLongSpan()
{
return InputSpan(long.Parse);
}
public static Span InputULongSpan()
{
return InputSpan(ulong.Parse);
}
public static string[] ReadLineSplit()
{
return Console.ReadLine()!.Split(' ');
}
public static IEnumerable InputEnumerable(Func parser)
{
return ReadLineSplit().Select(parser);
}
public static T[] InputArray(Converter parser)
{
return Array.ConvertAll(ReadLineSplit(), (a) => parser(a)).ToArray();
}
public static Span InputSpan(Converter parser) =>
InputArray(parser);
public static (T, T) InputTuple2(Converter parser)
{
var array = InputSpan(parser);
return (array[0], array[1]);
}
public static (T, T, T) InputTuple3(Converter parser)
{
var array = InputSpan(parser);
return (array[0], array[1], array[2]);
}
public static (T, T, T, T) InputTuple4(Converter parser)
{
var array = InputSpan(parser);
return (array[0], array[1], array[2], array[3]);
}
public static Span InputString()
{
return Console.ReadLine()!.ToCharArray();
}
public static int InputInt()
{
return int.Parse(Console.ReadLine()!);
}
public static long InputLong()
{
return long.Parse(Console.ReadLine()!);
}
public static ulong InputULong()
{
return ulong.Parse(Console.ReadLine()!);
}
public static void Yes()
{
Console.WriteLine("YES");
}
public static void No()
{
Console.WriteLine("NO");
}
public static string DoubleString(double val)
{
return val.ToString("F9");
}
#endregion
public static void Main(string[] args)
{
#if Sigma
using TextReader textReader = File.OpenText("input.txt");
Console.SetIn(textReader);
DateTime lastNow = DateTime.Now;
#endif
CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
Prepare();
int t = 1;
t = InputInt();
for (int i = 0; i < t; i++)
{
MainProblem();
}
#if Sigma
Console.WriteLine($"---------------");
Console.WriteLine($"Выполненно за {(DateTime.Now - lastNow).TotalMilliseconds} мс");
#endif
}
public static long Mod = 1_000_000_007L;
public static void Prepare()
{
}
public static void MainProblem()
{
}
}
```