using CpLibrary.Mathematics;
using CpLibrary.Util;
using System.Buffers;
using System.Buffers.Text;
using System.Collections;
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using static CpLibrary.StaticItems;
namespace CpLibrary.Contest
{
	public class SolverH : SolverBase
	{
		static void Main() => new SolverH().RunOnline();

		public override void Solve()
		{
			var (h, w) = sr.ReadValue<int, int>();
			var g = sr.ReadStringArray(h);
			var uf = new CpLibrary.Graph.UnionFind(h * w);
			for (int i = 0; i < h; i++)
			{
				for (int j = 0; j < w; j++)
				{
					if (i > 0 && g[i][j] == g[i - 1][j]) uf.Unite(i * w + j, (i - 1) * w + j);
					if (j > 0 && g[i][j] == g[i][j - 1]) uf.Unite(i * w + j, i * w + j - 1);
				}
			}
			var ans = CreateArray(h, w, (i, j) => g[i][j]);
			for (int i = 0; i < h; i++)
			{
				for (int j = 0; j < w; j++)
				{
					if (uf.Size(i * w + j) >= 4) ans[i][j] = '.';
				}
			}
			for (int i = 0; i < h; i++)
			{
				sw.WriteLine(ans[i].Join());
			}
		}

		public override void Init()
		{
			/*
			 * Write your init code here!
			 */
		}
	}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace CpLibrary { public interface ISolver { public void Run(StreamReader sr, StreamWriter sw); } }
namespace CpLibrary { public abstract class SolverBase : ISolver { public bool StartsOnThread { get; set; } = false; public int Testcases { get; set; } = 1;  public Scanner sr; public StreamWriter sw; public abstract void Init(); public abstract void Solve(); public void Run(StreamReader reader, StreamWriter writer) { this.sw = writer; sr = new Scanner(reader); Console.SetOut(writer); if (StartsOnThread) { var thread = new Thread(new ThreadStart(RunInternal), 1 << 27); thread.Start(); thread.Join(); } else { RunInternal(); } }  void RunInternal() { Init(); var testcases = Testcases; while (testcases-- > 0) { Solve(); } }  protected void RunOnline() { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; var sr = new StreamReader(Console.OpenStandardInput()); Run(sr, sw); Console.Out.Flush(); } } }
namespace CpLibrary { public static class Extension { public static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); public static string Join<T>(this IEnumerable<T> x, char separator) => string.Join(separator, x); public static int UpperBound<T>(this IList<T> list, T value) => list.BinarySearch(value, true, 0, list.Count, Comparer<T>.Default); public static int LowerBound<T>(this IList<T> list, T value) => list.BinarySearch(value, false, 0, list.Count, Comparer<T>.Default); public static int BinarySearch<T>(this IList<T> list, T value, bool isUpperBound, int index, int length, Comparer<T> comparer) { var low = index - 1; var high = index + length; while (high - low > 1) { var mid = low + (high - low) / 2; var res = comparer.Compare(list[mid], value); if (res < 0 || (isUpperBound && res == 0)) low = mid; else high = mid; }  return high; }  public static bool Chmax<T>(ref this T a, T b) where T : struct, IComparable<T> { if (a.CompareTo(b) >= 0) return false; a = b; return true; }  public static bool Chmin<T>(ref this T a, T b) where T : struct, IComparable<T> { if (a.CompareTo(b) <= 0) return false; a = b; return true; } } }
namespace CpLibrary.Graph { public static partial class Graph { public interface IEdge { int To { get; } }  public interface IWeightedEdge<T> : IEdge where T : INumber<T> { T Weight { get; } }  public interface IGraph<TEdge> where TEdge : IEdge { public List<TEdge> this[int index] { get; }  public int NodeCount { get; }  public List<TEdge> Next(int x); }  public interface IWeightedGraph<TEdge, TWeight> : IGraph<TEdge> where TWeight : INumber<TWeight> where TEdge : IWeightedEdge<TWeight> { }  public struct BasicEdge : IEdge { public int To { get; private set; }  public BasicEdge(int to) { this.To = to; }  public override string ToString() => $"{To}"; public static implicit operator BasicEdge(int edge) => new BasicEdge(edge); public static implicit operator int (BasicEdge edge) => edge.To; }  public struct WeightedEdge<T> : IWeightedEdge<T> where T : INumber<T> { public int To { get; private set; } public T Weight { get; private set; }  public WeightedEdge(int to, T weight) { To = to; Weight = weight; }  public WeightedEdge(int to) : this(to, default(T)) { }  public override string ToString() => $"[{Weight}] -> {To}"; public void Deconstruct(out int to, out T weight) => (to, weight) = (To, Weight); }  public class UndirectedGraph : IGraph<BasicEdge> { public readonly List<List<BasicEdge>> g; public List<BasicEdge> this[int index] => g[index]; public int NodeCount => g.Count;  public UndirectedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<BasicEdge>()).ToList(); public UndirectedGraph(int nodeCount, int[] u, int[] v) : this(nodeCount) { if (u.Length != v.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(v)} must have the same length."); for (var i = 0; i < u.Length; i++) { AddEdge(u[i], v[i]); } }  public void AddEdge(int u, int v) { g[u].Add(v); g[v].Add(u); }  public void AddNode() => g.Add(new List<BasicEdge>()); public List<BasicEdge> Next(int x) => g[x]; }  public class DirectedGraph : IGraph<BasicEdge> { public readonly List<List<BasicEdge>> g; public List<BasicEdge> this[int index] => g[index]; public int NodeCount => g.Count;  public DirectedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<BasicEdge>()).ToList(); public DirectedGraph(int nodeCount, int[] from, int[] to) : this(nodeCount) { if (from.Length != to.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(to)} must have the same length."); for (var i = 0; i < from.Length; i++) { AddEdge(from[i], to[i]); } }  public void AddEdge(int from, int to) => g[from].Add(to); public void AddNode() => g.Add(new List<BasicEdge>()); public List<BasicEdge> Next(int x) => g[x]; }  public class UndirectedWeightedGraph<T> : IWeightedGraph<WeightedEdge<T>, T> where T : INumber<T> { public readonly List<List<WeightedEdge<T>>> g; public List<WeightedEdge<T>> this[int index] => g[index]; public int NodeCount => g.Count;  public UndirectedWeightedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<WeightedEdge<T>>()).ToList(); public UndirectedWeightedGraph(int nodeCount, int[] u, int[] v, T[] weight) : this(nodeCount) { if (u.Length != v.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(v)} must have the same length."); if (u.Length != weight.Length) throw new ArgumentException($"The arrays {nameof(u)} and {nameof(weight)} must have the same length."); if (weight.Length != v.Length) throw new ArgumentException($"The arrays {nameof(v)} and {nameof(weight)} must have the same length."); for (var i = 0; i < u.Length; i++) { AddEdge(u[i], v[i], weight[i]); } }  public void AddEdge(int u, int v, T w) { g[u].Add(new WeightedEdge<T>(v, w)); g[v].Add(new WeightedEdge<T>(u, w)); }  public void AddNode() => g.Add(new List<WeightedEdge<T>>()); public List<WeightedEdge<T>> Next(int x) => g[x]; }  public class DirectedWeightedGraph<T> : IWeightedGraph<WeightedEdge<T>, T> where T : INumber<T> { public readonly List<List<WeightedEdge<T>>> g; public List<WeightedEdge<T>> this[int index] => g[index]; public int NodeCount => g.Count;  public DirectedWeightedGraph(int nodeCount) => g = Enumerable.Repeat(0, nodeCount).Select(_ => new List<WeightedEdge<T>>()).ToList(); public DirectedWeightedGraph(int nodeCount, int[] from, int[] to, T[] weight) : this(nodeCount) { if (from.Length != to.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(to)} must have the same length."); if (from.Length != weight.Length) throw new ArgumentException($"The arrays {nameof(from)} and {nameof(weight)} must have the same length."); if (weight.Length != to.Length) throw new ArgumentException($"The arrays {nameof(to)} and {nameof(weight)} must have the same length."); for (var i = 0; i < from.Length; i++) { AddEdge(from[i], to[i], weight[i]); } }  public void AddEdge(int from, int to, T w) { g[from].Add(new WeightedEdge<T>(to, w)); }  public void AddNode() => g.Add(new List<WeightedEdge<T>>()); public List<WeightedEdge<T>> Next(int x) => g[x]; } } }
namespace CpLibrary.Graph { public class UnionFind { public int Count { get; private set; }  int[] parent; int[] rank; int[] size; public UnionFind(int n) { parent = Enumerable.Range(0, n).ToArray(); rank = Enumerable.Repeat(0, n).ToArray(); size = Enumerable.Repeat(1, n).ToArray(); }  public void Unite(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; if (rank[x] > rank[y]) { parent[y] = x; size[x] += size[y]; } else { parent[x] = y; if (rank[x] == rank[y]) rank[x]++; size[y] += size[x]; } }  public int Find(int x) { if (parent[x] == x) return x; else return parent[x] = Find(parent[x]); }  public bool IsSame(int x, int y) => Find(x) == Find(y); public int Size(int x) => size[Find(x)]; } }
namespace CpLibrary { public class Scanner { public Stream stream { get; private set; }  byte[] buffer; int length; int index; readonly static byte[] DEFAULT_SEPARATORS = { (byte)'\n', (byte)'\r', (byte)'\t', (byte)' ' }; byte[] separators; public Scanner(Stream stream, byte[] separators, int size = 1 << 12) { this.stream = stream; this.separators = separators; buffer = GC.AllocateUninitializedArray<byte>(size); length = index = 0; }  public Scanner(Stream stream, int size = 1 << 12) : this(stream, DEFAULT_SEPARATORS, size) { }  public Scanner(int size = 1 << 12) : this(Console.OpenStandardInput(), DEFAULT_SEPARATORS, size) { }  public Scanner(StreamReader sr, byte[] separators, int size = 1 << 12) : this(sr.BaseStream, separators, size) { }  public Scanner(StreamReader sr, int size = 1 << 12) : this(sr.BaseStream, DEFAULT_SEPARATORS, size) { }  [MethodImpl(MethodImplOptions.AggressiveInlining)] static bool IsSeparator(byte c) => c <= ' '; [MethodImpl(MethodImplOptions.AggressiveInlining)] static bool IsNewLine(byte c) => c >= '\n' && c <= '\r'; void Fill() { if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; if (length < buffer.Length) buffer[length] = (byte)'\n'; }  while (IsSeparator(buffer[index])) { index++; if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; if (length < buffer.Length) buffer[length] = (byte)'\n'; } }  if (index + 64u >= length && !IsSeparator(buffer[^1])) { buffer.AsSpan(index, length - index).CopyTo(buffer); length -= index; index = 0; length = stream.Read(buffer, length, buffer.Length - length) + length; if (length < buffer.Length) buffer[length] = (byte)'\n'; } }  public Span<byte> ReadToken() { if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; }  while (IsSeparator(buffer[index])) { index++; if ((uint)index >= (uint)length) { length = stream.Read(buffer, 0, buffer.Length); index = 0; } }  var next = buffer.AsSpan(index, length - index).IndexOfAny(separators.AsSpan()); if (length < buffer.Length) { var p = index; index = (int)Math.Min((uint)(next), (uint)(length - index)) + index; return buffer.AsSpan(p, index - p); }  var pool = ArrayPool<byte>.Shared.Rent(buffer.Length); var pindex = 0; while (length > 0 && (uint)next >= (uint)length) { if (pool.Length - pindex < length - index) Resize(ref pool, pool.Length); buffer.AsSpan(index).CopyTo(pool.AsSpan(pindex)); pindex += length - index; length = stream.Read(buffer, 0, buffer.Length); index = 0; next = buffer.AsSpan(index, length - index).IndexOfAny(separators); }  if (next == -1) next = length; if (pool.Length - pindex < next) Resize(ref pool, pool.Length); buffer.AsSpan(index, next).CopyTo(pool.AsSpan(pindex)); pindex += next; index = next + index; try { return pool.AsSpan(0, pindex); } finally { ArrayPool<byte>.Shared.Return(pool); } }  void Resize<T>(ref T[] arr, int l) { var p = arr; arr = ArrayPool<T>.Shared.Rent(l << 1); p.AsSpan().CopyTo(arr); ArrayPool<T>.Shared.Return(p); }  public string Read() => Encoding.UTF8.GetString(ReadToken()); public string ReadString() => Read(); public string[] ReadStringArray(int n) { var arr = GC.AllocateUninitializedArray<string>(n); for (int i = 0; i < n; i++) { arr[i] = ReadString(); }  return arr; }  public uint ReadUInt() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out uint value, out int bc); index += bc; return value; }  public int ReadInt() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out int value, out int bc); index += bc; return value; }  public ulong ReadULong() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out ulong value, out int bc); index += bc; return value; }  public long ReadLong() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out long value, out int bc); index += bc; return value; }  public double ReadDouble() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out double value, out int bc); index += bc; return value; }  public decimal ReadDecimal() { Fill(); Utf8Parser.TryParse(buffer.AsSpan(index), out decimal value, out int bc); index += bc; return value; }  public int[] ReadIntArray(int n) => ReadValueArray<int>(n); public uint[] ReadUIntArray(int n) => ReadValueArray<uint>(n); public ulong[] ReadULongArray(int n) => ReadValueArray<ulong>(n); public long[] ReadLongArray(int n) => ReadValueArray<long>(n); public double[] ReadDoubleArray(int n) => ReadValueArray<double>(n); public decimal[] ReadDecimalArray(int n) => ReadValueArray<decimal>(n); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T ReadValue<T>() { if (typeof(T) == typeof(int)) return (T)(object)ReadInt(); if (typeof(T) == typeof(uint)) return (T)(object)ReadUInt(); if (typeof(T) == typeof(long)) return (T)(object)ReadLong(); if (typeof(T) == typeof(ulong)) return (T)(object)ReadULong(); if (typeof(T) == typeof(double)) return (T)(object)ReadDouble(); if (typeof(T) == typeof(decimal)) return (T)(object)ReadDecimal(); if (typeof(T) == typeof(string)) return (T)(object)ReadString(); throw new NotSupportedException(); }  public (T1, T2) ReadValue<T1, T2>() => (ReadValue<T1>(), ReadValue<T2>()); public (T1, T2, T3) ReadValue<T1, T2, T3>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>()); public (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>()); public (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>()); public (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>()); public (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>() => (ReadValue<T1>(), ReadValue<T2>(), ReadValue<T3>(), ReadValue<T4>(), ReadValue<T5>(), ReadValue<T6>(), ReadValue<T7>()); public T1[] ReadValueArray<T1>(int n) { var arr = GC.AllocateUninitializedArray<T1>(n); for (int i = 0; i < n; i++) { arr[i] = ReadValue<T1>(); }  return arr; }  public (T1[], T2[]) ReadValueArray<T1, T2>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i]) = ReadValue<T1, T2>(); }  return (a1, a2); }  public (T1[], T2[], T3[]) ReadValueArray<T1, T2, T3>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i]) = ReadValue<T1, T2, T3>(); }  return (a1, a2, a3); }  public (T1[], T2[], T3[], T4[]) ReadValueArray<T1, T2, T3, T4>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i]) = ReadValue<T1, T2, T3, T4>(); }  return (a1, a2, a3, a4); }  public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray<T1, T2, T3, T4, T5>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i]) = ReadValue<T1, T2, T3, T4, T5>(); }  return (a1, a2, a3, a4, a5); }  public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray<T1, T2, T3, T4, T5, T6>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); var a6 = GC.AllocateUninitializedArray<T6>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i], a6[i]) = ReadValue<T1, T2, T3, T4, T5, T6>(); }  return (a1, a2, a3, a4, a5, a6); }  public (T1[], T2[], T3[], T4[], T5[], T6[], T7[]) ReadValueArray<T1, T2, T3, T4, T5, T6, T7>(int n) { var a1 = GC.AllocateUninitializedArray<T1>(n); var a2 = GC.AllocateUninitializedArray<T2>(n); var a3 = GC.AllocateUninitializedArray<T3>(n); var a4 = GC.AllocateUninitializedArray<T4>(n); var a5 = GC.AllocateUninitializedArray<T5>(n); var a6 = GC.AllocateUninitializedArray<T6>(n); var a7 = GC.AllocateUninitializedArray<T7>(n); for (int i = 0; i < n; i++) { (a1[i], a2[i], a3[i], a4[i], a5[i], a6[i], a7[i]) = ReadValue<T1, T2, T3, T4, T5, T6, T7>(); }  return (a1, a2, a3, a4, a5, a6, a7); }  public (T1, T2)[] ReadTupleArray<T1, T2>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2>(); }  return ret; }  public (T1, T2, T3)[] ReadTupleArray<T1, T2, T3>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3>(); }  return ret; }  public (T1, T2, T3, T4)[] ReadTupleArray<T1, T2, T3, T4>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4>(); }  return ret; }  public (T1, T2, T3, T4, T5)[] ReadTupleArray<T1, T2, T3, T4, T5>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5>(); }  return ret; }  public (T1, T2, T3, T4, T5, T6)[] ReadTupleArray<T1, T2, T3, T4, T5, T6>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5, T6)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5, T6>(); }  return ret; }  public (T1, T2, T3, T4, T5, T6, T7)[] ReadTupleArray<T1, T2, T3, T4, T5, T6, T7>(int n) { var ret = GC.AllocateUninitializedArray<(T1, T2, T3, T4, T5, T6, T7)>(n); for (int i = 0; i < n; i++) { ret[i] = ReadValue<T1, T2, T3, T4, T5, T6, T7>(); }  return ret; } } }
namespace CpLibrary.Mathematics { [DebuggerDisplay("{ToString(), nq}")] public class Matrix<T> : IEquatable<Matrix<T>>, IEnumerable<T>, IEnumerable<IEnumerable<T>> where T : INumberBase<T> { int row; int column; public T[] value; public Matrix(int r, int c) : this(r, c, new T[r * c]) { }  public Matrix(int r, int c, IEnumerable<T> a) { value = a.ToArray(); row = r; column = c; }  public Matrix(int r, int c, T[] a) { value = a; row = r; column = c; }  public Matrix(T[][] a) { if (a is null || a.Length == 0) throw new ArgumentException("Input array cannot be null or empty.", nameof(a)); row = a.Length; column = a[0].Length; if (!a.Select(b => b.Length).All(x => x == column)) throw new ArgumentException("All rows must have the same length.", nameof(a)); value = a.SelectMany(x => x).ToArray(); }  public Matrix(T[, ] a) { if (a is null || a.Length == 0) throw new ArgumentException("Input array cannot be null or empty.", nameof(a)); row = a.GetLength(0); column = a.GetLength(1); value = a.Cast<T>().ToArray(); }  public Span<T> this[int r] {[MethodImpl(MethodImplOptions.AggressiveInlining)] get => value.AsSpan(r * column, column); }  public T this[int r, int c] {[MethodImpl(MethodImplOptions.AggressiveInlining)] get => value[r * column + c]; [MethodImpl(MethodImplOptions.AggressiveInlining)] set => this.value[r * column + c] = value; }  public T[][] Rows => ToRowArray();  public static Matrix<T> operator +(Matrix<T> lhs, Matrix<T> rhs) { if (lhs.row != rhs.row) throw new ArgumentException(); if (lhs.column != rhs.column) throw new ArgumentException(); var ret = new T[lhs.row * lhs.column]; for (int i = 0; i < lhs.row * lhs.column; i++) { ret[i] = lhs.value[i] + rhs.value[i]; }  return new Matrix<T>(lhs.row, lhs.column, ret); }  public static Matrix<T> operator -(Matrix<T> lhs, Matrix<T> rhs) { if (lhs.row != rhs.row) throw new ArgumentException(); if (lhs.column != rhs.column) throw new ArgumentException(); var ret = new T[lhs.row * lhs.column]; for (int i = 0; i < lhs.row * lhs.column; i++) { ret[i] = lhs.value[i] - rhs.value[i]; }  return new Matrix<T>(lhs.row, lhs.column, ret); }  public static Matrix<T> operator *(T k, Matrix<T> x) { var ret = new T[x.row * x.column]; for (int i = 0; i < x.row * x.column; i++) { ret[i] = k * x.value[i]; }  return new Matrix<T>(x.row, x.column, ret); }  public static Matrix<T> operator *(Matrix<T> x, T k) => k * x; public static Matrix<T> operator *(Matrix<T> l, Matrix<T> r) { if (l.column != r.row) throw new ArgumentException(); var rt = r.Transpose(); var lv = l.value; var rtv = rt.value; var ret = new T[l.row * r.column]; for (int i = 0; i < l.row; i++) { for (int j = 0; j < r.column; j++) { var sum = T.Zero; for (int k = 0; k < l.column; k++) { sum += lv[i * l.column + k] * rtv[j * rt.column + k]; }  ret[i * r.column + j] = sum; } }  return new Matrix<T>(l.row, r.column, ret); }  public static bool operator ==(Matrix<T> lhs, Matrix<T> rhs) => lhs.Equals(rhs); public static bool operator !=(Matrix<T> lhs, Matrix<T> rhs) => !(lhs == rhs); public Matrix<T> Pow(long n) => Pow(this, n); public static Matrix<T> Pow(Matrix<T> x, long n) { if (x.column != x.row) throw new ArgumentException(); var ret = new Matrix<T>(x.column, x.column); for (int i = 0; i < x.column; i++) { ret[i, i] = T.One; }  for (long i = 1; i <= n; i *= 2, x *= x) { if (n / i % 2 == 1) ret *= x; }  return ret; }  public Matrix<T> Transpose() { var res = new Matrix<T>(this.column, this.row); for (int i = 0; i < this.row; i++) { for (int j = 0; j < this.column; j++) { res[j, i] = this[i, j]; } }  return res; }  public T Determinant() { if (column != row) throw new ArgumentException(); var a = new T[row * column]; value.AsSpan().CopyTo(a); var swap = false; var p = Enumerable.Range(0, row).ToArray(); for (int i = 0; i < row; i++) { var ok = false; for (int j = i; j < row; j++) { if (a[p[j] * row + i] != T.Zero) { ok = true; if (i != j) { (p[i], p[j]) = (p[j], p[i]); swap = !swap; }  break; } }  if (!ok) return T.AdditiveIdentity; var t = a[p[i] * row + i]; for (int j = i + 1; j < row; j++) { var c = a[p[j] * row + i] / t; for (int k = 0; k < row; k++) { a[p[j] * row + k] -= c * a[p[i] * row + k]; } } }  var det = T.MultiplicativeIdentity; if (swap) det = -det; for (int i = 0; i < row; i++) { det *= a[p[i] * row + i]; }  return det; }  public T[][] ToRowArray() { var ret = new T[row][]; for (int i = 0; i < row; i++) { ret[i] = this[i].ToArray(); }  return ret; }  [MethodImpl(MethodImplOptions.AggressiveInlining)] public override bool Equals(object? obj) => obj is Matrix<T> x && Equals(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Equals(Matrix<T> other) { if (row != other.row) return false; if (column != other.column) return false; return value.AsSpan().SequenceEqual(other.value); }  [MethodImpl(MethodImplOptions.AggressiveInlining)] public override int GetHashCode() => HashCode.Combine(row, value); public override string ToString() { var sb = new StringBuilder(); for (int i = 0; i < row; i++) { sb.Append("{ "); for (int j = 0; j < column; j++) { sb.Append(this[i, j]); if (j < column - 1) { sb.Append(", "); } }  sb.Append(" }"); if (i < row - 1) { sb.AppendLine(); } }  return sb.ToString(); }  public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)value).GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); IEnumerator<IEnumerable<T>> IEnumerable<IEnumerable<T>>.GetEnumerator() { for (int i = 0; i < row; i++) { yield return GetRow(i); } }  IEnumerable<T> GetRow(int idx) { if (idx < 0 || row <= idx) throw new ArgumentException(); for (int i = 0; i < column; i++) { yield return value[idx * column + i]; } } } }
namespace CpLibrary { public static partial class StaticItems { public static bool NextPermutation<T>(IList<T> arr) where T : IComparable<T> { var p = -1; var q = -1; for (int i = 0; i < arr.Count - 1; i++) { if (arr[i].CompareTo(arr[i + 1]) < 0) p = i; }  if (p == -1) return false; for (int i = arr.Count - 1; i >= 0; i--) { if (arr[p].CompareTo(arr[i]) < 0) { q = i; break; } }  (arr[p], arr[q]) = (arr[q], arr[p]); for (int i = 0; p + 1 + i < arr.Count - 1 - i; i++) { (arr[p + 1 + i], arr[arr.Count - 1 - i]) = (arr[arr.Count - 1 - i], arr[p + 1 + i]); }  return true; } } }
namespace CpLibrary { public static partial class StaticItems { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(uint n) { n = (n & 0x55555555) + (n >> 1 & 0x55555555); n = (n & 0x33333333) + (n >> 2 & 0x33333333); n = (n & 0x0f0f0f0f) + (n >> 4 & 0x0f0f0f0f); n = (n & 0x00ff00ff) + (n >> 8 & 0x00ff00ff); n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff); return (int)n; }  [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(int n) => PopCount((uint)n); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(ulong n) { n = (n & 0x5555555555555555) + (n >> 1 & 0x5555555555555555); n = (n & 0x3333333333333333) + (n >> 2 & 0x3333333333333333); n = (n & 0x0f0f0f0f0f0f0f0f) + (n >> 4 & 0x0f0f0f0f0f0f0f0f); n = (n & 0x00ff00ff00ff00ff) + (n >> 8 & 0x00ff00ff00ff00ff); n = (n & 0x0000ffff0000ffff) + (n >> 16 & 0x0000ffff0000ffff); n = (n & 0x00000000ffffffff) + (n >> 32 & 0x00000000ffffffff); return (int)n; }  [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(long n) => PopCount((ulong)n); } }
namespace CpLibrary { public static partial class StaticItems { public static Graph.Graph.DirectedGraph NextGraph(this IRandom rand, int n, int m) { throw new NotImplementedException(); } } }
namespace CpLibrary { public static partial class StaticItems { public static T[][] ReadMatrix<T>(this Scanner sr, int n, int m) where T : ISpanParsable<T> => Enumerable.Range(0, n).Select(p => sr.ReadValueArray<T>(m)).ToArray(); public static T[][] ReadJaggedArray<T>(this Scanner sr, int n, int[] m) where T : ISpanParsable<T> => Enumerable.Range(0, n).Select(p => sr.ReadValueArray<T>(m[p])).ToArray(); } }
namespace CpLibrary { public static partial class StaticItems { public static int[] dx4 => new int[] { 1, 0, -1, 0 }; public static int[] dy4 => new int[] { 0, 1, 0, -1 }; public static int[] dx8 => new int[] { 1, 1, 0, -1, -1, -1, 0, 1 }; public static int[] dy8 => new int[] { 0, 1, 1, 1, 0, -1, -1, -1 };  public enum YesNoOption { Normal, Upper, Lower }  public static string YesNo(bool condition, YesNoOption option = YesNoOption.Normal) { if (option == YesNoOption.Normal) return YesNoNormal(condition); else if (option == YesNoOption.Upper) return YesNoUpper(condition); else if (option == YesNoOption.Lower) return YesNoLower(condition); else throw new ArgumentException(); }  public static string YesNoNormal(bool condition) => condition ? "Yes" : "No"; public static string YesNoUpper(bool condition) => condition ? "YES" : "NO"; public static string YesNoLower(bool condition) => condition ? "yes" : "no"; public static T SignOutput<T>(int x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T SignOutput<T>(long x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T SignOutput<T>(double x, T pos, T zero, T neg) => x == 0 ? zero : (x > 0 ? pos : neg); public static T[] CreateArray<T>(int n, Func<int, T> func) => Enumerable.Range(0, n).Select(p => func(p)).ToArray(); public static T[][] CreateArray<T>(int x, int y, Func<int, int, T> func) => Enumerable.Range(0, x).Select(i => Enumerable.Range(0, y).Select(j => func(i, j)).ToArray()).ToArray(); public static T[][][] CreateArray<T>(int x, int y, int z, Func<int, int, int, T> func) => Enumerable.Range(0, x).Select(i => Enumerable.Range(0, y).Select(j => Enumerable.Range(0, z).Select(k => func(i, j, k)).ToArray()).ToArray()).ToArray(); } }
namespace CpLibrary { public static partial class StaticItems { public static void WriteMatrix<T>(this StreamWriter sw, IEnumerable<IEnumerable<T>> arr) => sw.WriteLine(arr.Select(p => p.Join(" ")).Join("\n")); public static void WriteMatrix<T>(this StreamWriter sw, Matrix<T> arr) where T : INumberBase<T> => sw.WriteMatrix((IEnumerable<IEnumerable<T>>)arr); } }
namespace CpLibrary.Util { public interface IRandom { public int Next(); public int Next(int b); public int Next(int a, int b); public void NextBytes(byte[] b); public void NextBytes(Span<byte> b); public double NextDouble(); public long NextLong(); public long NextLong(long b); public long NextLong(long a, long b); } }
#endregion Expanded by https://github.com/kzrnm/SourceExpander