結果
| 問題 | No.3013 ハチマキ買い星人 |
| ユーザー |
 Lidelie
|
| 提出日時 | 2025-01-25 14:58:53 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 722 ms / 2,000 ms |
| コード長 | 34,748 bytes |
| コンパイル時間 | 14,571 ms |
| コンパイル使用メモリ | 170,492 KB |
| 実行使用メモリ | 237,240 KB |
| 最終ジャッジ日時 | 2025-01-25 23:38:25 |
| 合計ジャッジ時間 | 32,387 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 45 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (92 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections;
//using System.Linq;
using System.Collections.Generic;
using LidelieLibrary;
using static LidelieLibrary.Input;
using static LidelieLibrary.Functions;
using static LidelieLibrary.MathExt;
using System.IO;
using System.Text;
using System.Numerics;
class Solver{
static void Main(string[] args){
var(n,m,p,y)=Assign<int,int,int,long>();
var e = new Dictionary<int,List<(int to,long cost)>>();
for(int i = 0;i<n;i++){
e.Add(i,new List<(int to, long cost)>());
}
for(int i = 0;i<m;i++){
var (a,b,c)=Assign<int,int,long>();
a--;b--;
Add(e,a,(b,c));
Add(e,b,(a,c));
}
var costs = new long[n];
long large = Powl(10,18)+Powl(10,17);
for(int i = 1;i<n;i++)costs[i]=large;
var pq = new PriorityQueue<int,long>();
pq.Enqueue(0,0);
var vis = new bool[n];
int confirmed = 0;
while(pq.Count>0&&confirmed<n){
int foc = pq.Dequeue();
if(vis[foc])continue;
vis[foc]=true;
confirmed++;
foreach((int to,long cost) in e[foc]){
if(costs[to]>costs[foc]+cost&&!vis[to]){
costs[to]=costs[foc]+cost;
pq.Enqueue(to,costs[to]);
}
}
}
long ans = 0;
for(int i = 0;i<p;i++){
var(d,price)=Assign<int,long>();
d--;
ans = Math.Max(ans,(Math.Max(0,y-costs[d]))/price);
}
Out(ans);
}
}
public class MultiSet<T> : Set<T> where T : IComparable
{
public override void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else _root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public class SB_BinarySearchTree<T> where T : IComparable
{
public class Node
{
public T Value;
public Node LChild;
public Node RChild;
public int Count; //size of the sub tree
public Node(T v)
{
Value = v;
Count = 1;
}
}
static Random _rnd = new Random();
public static int Count(Node t)
{
return t == null ? 0 : t.Count;
}
static Node Update(Node t)
{
t.Count = Count(t.LChild) + Count(t.RChild) + 1;
return t;
}
public static Node Merge(Node l, Node r)
{
if (l == null || r == null) return l == null ? r : l;
if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
{
l.RChild = Merge(l.RChild, r);
return Update(l);
}
else
{
r.LChild = Merge(l, r.LChild);
return Update(r);
}
}
/// <summary>
/// split as [0, k), [k, n)
/// </summary>
public static Tuple<Node, Node> Split(Node t, int k)
{
if (t == null) return new Tuple<Node, Node>(null, null);
if (k <= Count(t.LChild))
{
var s = Split(t.LChild, k);
t.LChild = s.Item2;
return new Tuple<Node, Node>(s.Item1, Update(t));
}
else
{
var s = Split(t.RChild, k - Count(t.LChild) - 1);
t.RChild = s.Item1;
return new Tuple<Node, Node>(Update(t), s.Item2);
}
}
public static Node Remove(Node t, T v)
{
if (Find(t, v) == null) return t;
return RemoveAt(t, LowerBound(t, v));
}
public static Node RemoveAt(Node t, int k)
{
var s = Split(t, k);
var s2 = Split(s.Item2, 1);
return Merge(s.Item1, s2.Item2);
}
public static bool Contains(Node t, T v)
{
return Find(t, v) != null;
}
public static Node Find(Node t, T v)
{
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0) t = t.LChild;
else if (cmp < 0) t = t.RChild;
else break;
}
return t;
}
public static Node FindByIndex(Node t, int idx)
{
if (t == null) return null;
var currentIdx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
if (currentIdx == idx) return t;
if (currentIdx > idx)
{
t = t.LChild;
currentIdx -= (Count(t == null ? null : t.RChild) + 1);
}
else
{
t = t.RChild;
currentIdx += (Count(t == null ? null : t.LChild) + 1);
}
}
return null;
}
public static int UpperBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var ret = Int32.MaxValue;
var idx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0)
{
ret = Math.Min(ret, idx);
t = t.LChild;
idx -= (Count(t == null ? null : t.RChild) + 1);
}
else if (cmp <= 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
}
}
return ret == Int32.MaxValue ? Count(torg) : ret;
}
public static int LowerBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var idx = Count(t) - Count(t.RChild) - 1;
var ret = Int32.MaxValue;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp >= 0)
{
if (cmp == 0) ret = Math.Min(ret, idx);
t = t.LChild;
if (t == null) ret = Math.Min(ret, idx);
idx -= t == null ? 0 : (Count(t.RChild) + 1);
}
else if (cmp < 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
if (t == null) return idx;
}
}
return ret == Int32.MaxValue ? Count(torg) : ret;
}
public static Node Insert(Node t, T v)
{
var ub = LowerBound(t, v);
return InsertByIdx(t, ub, v);
}
static Node InsertByIdx(Node t, int k, T v)
{
var s = Split(t, k);
return Merge(Merge(s.Item1, new Node(v)), s.Item2);
}
public static IEnumerable<T> Enumerate(Node t)
{
var ret = new List<T>();
Enumerate(t, ret);
return ret;
}
static void Enumerate(Node t, List<T> ret)
{
if (t == null) return;
Enumerate(t.LChild, ret);
ret.Add(t.Value);
Enumerate(t.RChild, ret);
}
}
public class Set<T> where T : IComparable
{
protected SB_BinarySearchTree<T>.Node _root;
public T this[int idx]{ get { return ElementAt(idx); } }
public int Count()
{
return SB_BinarySearchTree<T>.Count(_root);
}
public virtual void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else
{
if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
_root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public void Clear()
{
_root = null;
}
public void Remove(T v)
{
_root = SB_BinarySearchTree<T>.Remove(_root, v);
}
public bool Contains(T v)
{
return SB_BinarySearchTree<T>.Contains(_root, v);
}
public T ElementAt(int k)
{
var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
if (node == null) throw new IndexOutOfRangeException();
return node.Value;
}
public int Count(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int LowerBound(T v)
{
return SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int UpperBound(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v);
}
public Tuple<int, int> EqualRange(T v)
{
if (!Contains(v)) return new Tuple<int, int>(-1, -1);
return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
}
public List<T> ToList()
{
return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
}
}
class Cmp : IComparer {
readonly long[] a;
readonly long[] b;
public Cmp(long[] aa,long[] bb){
a = aa;
b = bb;
}
public int Compare(object x,object y){
int i = (int)x;
int j = (int)y;
int r;
if((a[i]*(a[j]+b[j]))<a[j]*(a[i]+b[i]))r=10;
else r = -10;
if((a[i]*(a[j]+b[j]))==a[j]*(a[i]+b[i])){
if(i<j)r=-1;
else r=1;
}
return r ;
}
}
namespace LidelieLibrary{
class Annulus<T>{
public readonly int Length;
public Annulus(T[] arr){
Length=arr.Length;
}
int RevolveCW(int from,int count){return (from+count)%Length;}
int RevolveCCW(int from,int count){return (from-count)%Length;}
}
class SegmentTree{
public readonly int Size;
public long[] SegTree;
Func<long,long,long> Updator;
public SegmentTree(long[] arr,long init,Func<long,long,long> updator){
int p = PowerOfTwo(arr.Length);
Size = (int)Math.Pow(2,p);
SegTree = new long[2*Size];
for(int i = 0;i<Size;i++){
if(i<arr.Length)SegTree[Size+i]=arr[i];
else SegTree[Size+i]=init;
}
Updator = updator;
for(int i = Size-1;i>=1;i--){
SegTree[i] = Updator(SegTree[2*i],SegTree[2*i+1]);
}
}
public void Access(int index,long num){
SegTree[Size+index] = num;
Update(Size+index);
}
public int Index(int i){return Size+i;}
void Update(int p){
int i=p/2;
SegTree[i] = Updator(SegTree[2*i],SegTree[2*i+1]);
if(i==1)return;
Update(i);
}
public List<long> Segment(int l,int r){
l = Size+l;
r = Size+r;
int s = l;
var res = new List<long>();
while(s<r){
int ind = s;
int range = 1;
while(ind%2==0){
if(s+range*2>=r)break;
ind = ind/2;
range=range*2;
}
s = s+range;
res.Add(SegTree[ind]);
}
return res;
}
}
class Dimension{
public readonly int H;
public readonly int W;
public Dimension(int h,int w){
H=h;
W=w;
}
public int Lower(int i,int j){return W*i+j;}
public (int,int) Upper(int i){return(i/W,i%W);}
public bool IsRange(int i,int j){
if(0<=i&&i<H&&0<=j&&j<W)return true;
else return false;
}
public bool IsRange((int i,int j) p){
if(0<=p.i&&p.i<H&&0<=p.j&&p.j<W)return true;
else return false;
}
}
class UnionFind{
public readonly int Size;
public int[] Parent;
public int[] TreeSize;
public UnionFind(int size){
Size = size;
Parent = new int[size];
TreeSize = new int[size];
for(int i = 0;i<size;i++){
Parent[i]=-1;
TreeSize[i]=1;
}
}
private void Follow(int a,int b){
//if(Parent[a]!=b)TreeSize[b]+=GetTreeSize(Root(a));
Parent[a]=b;
}
public void BeRoot(int a){
Parent[a]=a;
}
public int GetTreeSize(int a){
return TreeSize[Root(a)];
}
public void Connect(int a,int b){
int aSize = GetTreeSize(Root(a));
int rootA = Root(a);
int rootB = Root(b);
if(rootA!=rootB)TreeSize[rootB]+=aSize;
Follow(rootA,rootB);
}
public int Root(int a){
if(Parent[a]==-1)return -1;
if(Parent[a]==a)return a;
return Parent[a]=Root(Parent[a]);
}
}
class Functions{
public static int Mod(int a,int b){
int res = a%b;
if(res<0)res+=b;
return res;
}
public static long Mod(long a,long b){
long res = a%b;
if(res<0)res+=b;
return res;
}
public static void Add<TKey,TValue>(Dictionary<TKey,TValue> dic,TKey key,TValue value)
where TValue : INumber<TValue>{
if(dic.ContainsKey(key))dic[key]+=value;
else dic.Add(key,value);
}
public static void Add<TKey,TValue>(Dictionary<TKey,List<TValue>> dic,TKey key,TValue value)
{//where TValue : INumber<TValue>{
if(dic.ContainsKey(key))dic[key].Add(value);
else{
dic.Add(key,new List<TValue>());
dic[key].Add(value);
}
}
public static char[] Reverse(char[] c){
for(int i = 0;i<c.Length/2;i++){
(c[i],c[c.Length-1-i])=(c[c.Length-1-i],c[i]);
}
return c;
}
public static string Reverse(string s){
char[] c = s.ToCharArray();
for(int i = 0;i<c.Length/2;i++){
(c[i],c[c.Length-1-i])=(c[c.Length-1-i],c[i]);
}
return new string(c);
}
public static bool IsPalindrome(char[] c){
bool flg = true;
for(int i = 0;i<c.Length/2;i++){
if(c[i]!=c[^(i+1)])flg=false;
}
return flg;
}
public static long PowerOfTwo(long a){
for(int i = 62;i>=0;i--){
if(((a>>i)&1)==1)return i+1;
}
return 0;
}
public static int PowerOfTwo(int a){
for(int i = 30;i>=0;i--){
if(((a>>i)&1)==1)return i+1;
}
return 0;
}
public static double Distance(int ax,int ay,int bx,int by){
return Math.Sqrt(Math.Pow(ax-bx,2)+Math.Pow(ay-by,2));
}
public static double Distance(double ax,double ay,double bx,double by){
return Math.Sqrt(Math.Pow(ax-bx,2)+Math.Pow(ay-by,2));
}
public static double Distance((int x,int y)a,(int x,int y)b){
return Math.Sqrt(Math.Pow(a.x-b.x,2)+Math.Pow(a.y-b.y,2));
}
public static double Distance(int ax,int ay,int az,int bx,int by,int bz){
return Math.Pow(Math.Pow(ax-bx,2)+Math.Pow(ay-by,2)+Math.Pow(az-bz,2),1/3);
}
public static int LowerBound(int[] array,int targ){
var ok = array.Length;
var ng = -1;
var m = 0;
while(ok-ng>1){
m = ng + (ok-ng)/2;
if(array[m]>=targ)ok = m;
else ng = m;
}
return ok;
}
public static int LowerBound(long[] array,long targ){
var ok = array.Length;
var ng = -1;
var m = 0;
while(ok-ng>1){
m = ng + (ok-ng)/2;
if(array[m]>=targ)ok = m;
else ng = m;
}
return ok;
}
public static int LowerBound(List<long> list,long targ){
var ok = list.Count;
var ng = -1;
var m = 0;
while(ok-ng>1){
m = ng + (ok-ng)/2;
if(list[m]>=targ)ok = m;
else ng = m;
}
return ok;
}
}
class MathExt{
public static long Powl(long a,long b){
long res = 1;
for(int i = 0;i<b;i++){
res *= a;
}
//if(a==0&&b==0)return 0;
return res;
}
/// <summary>
/// Enumerate primes that n or less.
/// BEWARE OF MLE
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static List<long> Primes(long n){
if(n>12000000){
Console.WriteLine("Are you going to break your PC?");
Console.WriteLine("(Input:"+n+")");
return new List<long>();
}
var res = new List<long>();
var set = new HashSet<long>();
for(int i = 2;i<=n;i++)
set.Add(i);
long k = 2;
while(k<=n){
for(long i = 2*k;i<=n;i+=k){
set.Remove(i);
}
k++;
while(!set.Contains(k)&&k<=n){
k++;
}
}
foreach(long l in set)res.Add(l);
return res;
}
public static Dictionary<long,int> PrimeFactorize(long n,List<long> primes){//damekamo
var res = new Dictionary<long,int>();
long val = n;
foreach(long p in primes){
if(p>n/2)break;
while(val%p==0){
val/=p;
Add(res,p,1);
}
}
if(val!=1&&!res.ContainsKey(val))Add(res,val,1);
return res;
}
public static long Factorial(long n){
long res = 1;
for(long i = 2;i<=n;i++)res*=i;
return res;
}
public static int P(int n,int r){
int res = 1;
for(int i = n;i>n-r;i--)res *= i;
return res;
}
public static int C(int n,int r){
int res = 1;
for(int i = n;i>n-r;i--)res *= i;
for(int i = r;i>1;i--)res /= i;
return res;
}
public static long C(long n,long r){
long res = 1;
for(long i = n;i>n-r;i--)res *= i;
for(long i = r;i>1;i--)res /= i;
return res;
}
public static long gcd(long a,long b){
if(a<b)(a,b)=(b,a);
return a%b==0?b:gcd(b,a%b);
}
public static long lcm(long a,long b){
return Math.Abs(a/gcd(a,b) *b);
}
// public static T[][] Permutation<T>(T[] array,int r){
// int n = array.Length;
// int cnt = P(n,r);
// T[][] res = new T[cnt][];
// for(int i = 0;i<res.Length;i++){
// res[i] = new T[r];
// }
// int created = 0;
// var l = new List<T>();
// var chosen = new HashSet<T>();
// for(int i = 0;i<array.Length;i++){
// DFS
// }
// void DFS(int depth){
// for(int i =)
// }
// }
/// <summary>
/// Enumerate Combinations of choosing r items from an array.
/// </summary>
/// <returns>An jagged array.</returns>
public static int[][] Combination(int[] array,int r){
int n = array.Length;
int[][] res = new int[C(n,r)][];
for(int i = 0;i<res.Length;i++){
res[i] = new int[r];
}
int created = 0;
var l = new List<int>();
for(int i = 0;i<=n-r;i++){
DFS(i,0);
}
void DFS(int i,int k) {
l.Add(array[i]);
if(k==r-1){
res[created]=l.ToArray();
created++;
}
else for(int j = i+1;j<=n-r+k+1;j++){
DFS(j,k+1);
}
l.RemoveAt(l.Count-1);
}
return res;
}
public static long[][] Combination(long[] array,long r){
int n = array.Length;
long[][] res = new long[C(n,r)][];
for(int i = 0;i<res.Length;i++){
res[i] = new long[r];
}
int created = 0;
var l = new List<long>();
for(int i = 0;i<=n-r;i++){
DFS(i,0);
}
void DFS(int i,int k) {
l.Add(array[i]);
if(k==r-1){
res[created]=l.ToArray();
created++;
}
else for(int j = i+1;j<=n-r+k+1;j++){
DFS(j,k+1);
}
l.RemoveAt(l.Count-1);
}
return res;
}
public static T[][] Combination<T>(T[] array,long r){
int n = array.Length;
T[][] res = new T[C(n,r)][];
for(int i = 0;i<res.Length;i++){
res[i] = new T[r];
}
int created = 0;
var l = new List<T>();
for(int i = 0;i<=n-r;i++){
DFS(i,0);
}
void DFS(int i,int k) {
l.Add(array[i]);
if(k==r-1){
res[created]=l.ToArray();
created++;
}
else for(int j = i+1;j<=n-r+k+1;j++){
DFS(j,k+1);
}
l.RemoveAt(l.Count-1);
}
return (T[][])res;
}
}
class Input{
public static void Out((int,int) arg){Console.WriteLine(arg.Item1+" "+arg.Item2);}
public static void Out((long,long) arg){Console.WriteLine(arg.Item1+' '+arg.Item2);}
public static void Out(List<int> arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(List<long> arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(List<string> arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(List<char> arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(int[] arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(long[] arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(string[] arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(char[] arg){Console.WriteLine(string.Join(' ',arg));}
public static void Out(object arg){Console.WriteLine(arg);}
public static void Yes(){Console.WriteLine("Yes");}
public static void No(){Console.WriteLine("No");}
static Queue<string> input = new Queue<string>();
public static T Assign<T>(){
object re = null;
if(typeof(T) == typeof(string[]))re = Console.ReadLine().Split(' ');
//if(typeof(T) == typeof(char[]))re = Array.ConvertAll(Console.ReadLine().Split(' '),char.Parse);
if(typeof(T) == typeof(int[]))re = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
if(typeof(T) == typeof(long[]))re = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
if(typeof(T) == typeof(float[]))re = Array.ConvertAll(Console.ReadLine().Split(' '),float.Parse);
if(typeof(T) == typeof(double[]))re = Array.ConvertAll(Console.ReadLine().Split(' '),double.Parse);
if(re!=null){
return (T)re;
}
if(input.Count == 0){
foreach(string item in Console.ReadLine().Split(' ')){
input.Enqueue(item);
}
}
if(typeof(T) == typeof(string))re = input.Dequeue();
if(typeof(T) == typeof(char))re = char.Parse(input.Dequeue());
if(typeof(T) == typeof(char[]))re = input.Dequeue().ToCharArray();
if(typeof(T) == typeof(int))re = int.Parse(input.Dequeue());
if(typeof(T) == typeof(long))re = long.Parse(input.Dequeue());
if(typeof(T) == typeof(ulong))re = ulong.Parse(input.Dequeue());
if(typeof(T) == typeof(float))re = float.Parse(input.Dequeue());
if(typeof(T) == typeof(double))re = double.Parse(input.Dequeue());
return (T)re;
}
public static (T1,T2) Assign<T1,T2>(){
while(input.Count < 2){
foreach(string item in Console.ReadLine().Split(' ')){
input.Enqueue(item);
}
}
(object a,object b) re = (null,null);
if(typeof(T1) == typeof(string))re.a = input.Dequeue();
if(typeof(T1) == typeof(char))re.a = char.Parse(input.Dequeue());
if(typeof(T1) == typeof(char[]))re.a = input.Dequeue().ToCharArray();
if(typeof(T1) == typeof(int))re.a = int.Parse(input.Dequeue());
if(typeof(T1) == typeof(long))re.a = long.Parse(input.Dequeue());
if(typeof(T1) == typeof(ulong))re.a = ulong.Parse(input.Dequeue());
if(typeof(T1) == typeof(float))re.a = float.Parse(input.Dequeue());
if(typeof(T1) == typeof(double))re.a = double.Parse(input.Dequeue());
if(typeof(T2) == typeof(string))re.b = input.Dequeue();
if(typeof(T2) == typeof(char))re.b = char.Parse(input.Dequeue());
if(typeof(T2) == typeof(char[]))re.b = input.Dequeue().ToCharArray();
if(typeof(T2) == typeof(int))re.b = int.Parse(input.Dequeue());
if(typeof(T2) == typeof(long))re.b = long.Parse(input.Dequeue());
if(typeof(T2) == typeof(ulong))re.b = ulong.Parse(input.Dequeue());
if(typeof(T2) == typeof(float))re.b = float.Parse(input.Dequeue());
if(typeof(T2) == typeof(double))re.b = double.Parse(input.Dequeue());
return ((T1,T2))re;
}
public static (T1,T2,T3) Assign<T1,T2,T3>(){
while(input.Count < 3){
foreach(string item in Console.ReadLine().Split(' ')){
input.Enqueue(item);
}
}
(object a,object b,object c) re = (null,null,null);
if(typeof(T1) == typeof(string))re.a = input.Dequeue();
if(typeof(T1) == typeof(char))re.a = char.Parse(input.Dequeue());
if(typeof(T1) == typeof(char[]))re.a = input.Dequeue().ToCharArray();
if(typeof(T1) == typeof(int))re.a = int.Parse(input.Dequeue());
if(typeof(T1) == typeof(long))re.a = long.Parse(input.Dequeue());
if(typeof(T1) == typeof(ulong))re.a = ulong.Parse(input.Dequeue());
if(typeof(T1) == typeof(float))re.a = float.Parse(input.Dequeue());
if(typeof(T1) == typeof(double))re.a = double.Parse(input.Dequeue());
if(typeof(T2) == typeof(string))re.b = input.Dequeue();
if(typeof(T2) == typeof(char))re.b = char.Parse(input.Dequeue());
if(typeof(T2) == typeof(char[]))re.b = input.Dequeue().ToCharArray();
if(typeof(T2) == typeof(int))re.b = int.Parse(input.Dequeue());
if(typeof(T2) == typeof(long))re.b = long.Parse(input.Dequeue());
if(typeof(T2) == typeof(ulong))re.b = ulong.Parse(input.Dequeue());
if(typeof(T2) == typeof(float))re.b = float.Parse(input.Dequeue());
if(typeof(T2) == typeof(double))re.b = double.Parse(input.Dequeue());
if(typeof(T3) == typeof(string))re.c = input.Dequeue();
if(typeof(T3) == typeof(char))re.c = char.Parse(input.Dequeue());
if(typeof(T3) == typeof(char[]))re.c = input.Dequeue().ToCharArray();
if(typeof(T3) == typeof(int))re.c = int.Parse(input.Dequeue());
if(typeof(T3) == typeof(long))re.c = long.Parse(input.Dequeue());
if(typeof(T3) == typeof(ulong))re.c = ulong.Parse(input.Dequeue());
if(typeof(T3) == typeof(float))re.c = float.Parse(input.Dequeue());
if(typeof(T3) == typeof(double))re.c = double.Parse(input.Dequeue());
return ((T1,T2,T3))re;
}
public static (T1,T2,T3,T4) Assign<T1,T2,T3,T4>(){
while(input.Count < 4){
foreach(string item in Console.ReadLine().Split(' ')){
input.Enqueue(item);
}
}
(object a,object b,object c,object d) re = (null,null,null,null);
if(typeof(T1) == typeof(string))re.a = input.Dequeue();
if(typeof(T1) == typeof(char))re.a = char.Parse(input.Dequeue());
if(typeof(T1) == typeof(char[]))re.a = input.Dequeue().ToCharArray();
if(typeof(T1) == typeof(int))re.a = int.Parse(input.Dequeue());
if(typeof(T1) == typeof(long))re.a = long.Parse(input.Dequeue());
if(typeof(T1) == typeof(ulong))re.a = ulong.Parse(input.Dequeue());
if(typeof(T1) == typeof(float))re.a = float.Parse(input.Dequeue());
if(typeof(T1) == typeof(double))re.a = double.Parse(input.Dequeue());
if(typeof(T2) == typeof(string))re.b = input.Dequeue();
if(typeof(T2) == typeof(char))re.b = char.Parse(input.Dequeue());
if(typeof(T2) == typeof(char[]))re.b = input.Dequeue().ToCharArray();
if(typeof(T2) == typeof(int))re.b = int.Parse(input.Dequeue());
if(typeof(T2) == typeof(long))re.b = long.Parse(input.Dequeue());
if(typeof(T2) == typeof(ulong))re.b = ulong.Parse(input.Dequeue());
if(typeof(T2) == typeof(float))re.b = float.Parse(input.Dequeue());
if(typeof(T2) == typeof(double))re.b = double.Parse(input.Dequeue());
if(typeof(T3) == typeof(string))re.c = input.Dequeue();
if(typeof(T3) == typeof(char))re.c = char.Parse(input.Dequeue());
if(typeof(T3) == typeof(char[]))re.c = input.Dequeue().ToCharArray();
if(typeof(T3) == typeof(int))re.c = int.Parse(input.Dequeue());
if(typeof(T3) == typeof(long))re.c = long.Parse(input.Dequeue());
if(typeof(T3) == typeof(ulong))re.c = ulong.Parse(input.Dequeue());
if(typeof(T3) == typeof(float))re.c = float.Parse(input.Dequeue());
if(typeof(T3) == typeof(double))re.c = double.Parse(input.Dequeue());
if(typeof(T4) == typeof(string))re.d = input.Dequeue();
if(typeof(T4) == typeof(char))re.d = char.Parse(input.Dequeue());
if(typeof(T4) == typeof(char[]))re.d = input.Dequeue().ToCharArray();
if(typeof(T4) == typeof(int))re.d = int.Parse(input.Dequeue());
if(typeof(T4) == typeof(long))re.d = long.Parse(input.Dequeue());
if(typeof(T4) == typeof(ulong))re.d = ulong.Parse(input.Dequeue());
if(typeof(T4) == typeof(float))re.d = float.Parse(input.Dequeue());
if(typeof(T4) == typeof(double))re.d = double.Parse(input.Dequeue());
return ((T1,T2,T3,T4))re;
}
/// <summary>
/// If 'grid[ i , j ]' matches 'subject', its coordinate will be listed to list.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="h"></param>
/// <param name="w"></param>
/// <param name="makeEdge"></param>
/// <param name="l"></param>
/// <param name="subject"></param>
/// <returns></returns>
public static T AssignGrid<T>(int h,int w,bool makeEdge = false){
object re = null;
if(typeof(T) == typeof(char[][]) && makeEdge==true){
char[][] grid = new char[h+2][];
grid[0]=new char[w+2];
grid[h+1]=new char[w+2];
for(int i = 1;i<=h;i++){
grid[i] = new char[w+2];
char[] c = Console.ReadLine().ToCharArray();
for(int j = 1;j<=w;j++){
grid[i][j]=c[j-1];
}
}
re = grid;
}
if(typeof(T) == typeof(char[][]) && makeEdge!=true){
char[][] grid = new char[h][];
for(int i = 0;i<h;i++){
grid[i] = Console.ReadLine().ToCharArray();
}
re = grid;
}
if(typeof(T) == typeof(char[,]) && makeEdge==true){
char[,] grid = new char[h+2,w+2];
for(int i = 1;i<=h;i++){
char[] c = Console.ReadLine().ToCharArray();
for(int j = 1;j<=w;j++){
grid[i,j]=c[j-1];
}
}
re = grid;
}
if(typeof(T) == typeof(char[,]) && makeEdge!=true){
char[,] grid = new char[h,w];
for(int i = 0;i<h;i++){
char[] c = Console.ReadLine().ToCharArray();
for(int j = 0;j<w;j++){
grid[i,j]=c[j];
}
}
re = grid;
}
return (T)re;
}
public static List<(int,int)> ListUp(char[][] g,char targ){
int h = g.Length;
int w = g[0].Length;
var l = new List<(int,int)>();
for(int i = 0;i<h;i++){
for(int j = 0;j<w;j++){
if(g[i][j]==targ){
l.Add((i,j));
}
}
}
return l;
}
public static List<(int,int)> ListUp(int[][] g,int targ){
int h = g.Length;
int w = g[0].Length;
var l = new List<(int,int)>();
for(int i = 0;i<h;i++){
for(int j = 0;j<w;j++){
if(g[i][j]==targ){
l.Add((i,j));
}
}
}
return l;
}
public static T[][] InitJagged<T>(int size1,int size2){
T[][] c = new T[size1][];
for(int i = 0;i<size1;i++)
c[i] = new T[size2];
return (T[][])c;
}
public static char[][] InitJaggedWith(int size1,int size2,char init){
char[][] c = new char[size1][];
for(int i = 0;i<size1;i++)
c[i] = new char[size2];
for(int i = 0;i<size1;i++){
for(int j = 0;j<size2;j++){
c[i][j]=init;
}
}
return c;
}
public static void OutGrid(char[][] g){
int h = g.Length;
for(int i = 0;i<h;i++){
Console.WriteLine(new string(g[i]));
}
}
}
}