import java.io.*;
import java.util.*;
public class Sateliti {
public static long p = 2; public static int q = 3; public static long r = 7; public static long M = (long) (1e9)+9;
public static int num; public static int m;
public static long[][] hash; public static long[][] prefix;
public static void main(String[] args) throws IOException {
FastIO io = new FastIO(); num = io.nextInt(); m = io.nextInt();
int[][] arr = new int[num*2][m*2]; //Create four neighboring copies which makes processing column/row shifts as just a sub-matrix query
for (int i = 0;i<num;i++) {
String s = io.next();
for (int j = 0;j<m;j++) {
int add = (s.charAt(j)=='*') ? 11 : 5;
arr[i][j] = add; arr[i+num][j] = add; arr[i][j+m] = add; arr[i+num][j+m] = add;
}
}
hash = hash(arr); prefix = new long[num*2][m*2]; prefix[0][0] = hash[0][0];
for (int i = 1;i<num*2;i++) prefix[i][0] = prefix[i-1][0]+hash[i][0];
for (int j = 1;j<m*2;j++) prefix[0][j] = prefix[0][j-1]+hash[0][j];
for (int i = 1;i<num*2;i++) {
for (int j = 1;j<m*2;j++) {
prefix[i][j] = (prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+hash[i][j])%M;
}
}
/*for (int i = 0;i<num*2;i++) {
for (int j = 0;j<m*2;j++) {
io.print(prefix[i][j]+" ");
}
io.println();
}*/
long[] rowHash = new long[num*2]; rowHash[0] = getHash(0,)
for (int i = 0;i<num*2;i++) rowHash[i] = (rowHash[i-1]+pow(r,i))%M;
int x = 0; int y = 0; //The answer sub-matrix
for (int i = 0;i<num;i++) {
for (int j = 0;j<m;j++) {
int l = 0; int h = num-1; //Find the first different row
while (l<h) {
int mid = (l+h)/2;
if (getHash(x+mid,y,x+mid,y+m-1)==getHash(i+mid,j,i+mid,j+m-1)) {
l = mid+1;
} else {
h = mid;
}
}
int r = l;
l = 0; h = m-1; //Find the first different column within row r.
while (l<h) {
int mid = (l+h)/2;
if (getHash(x+r,y,x+r,y+mid)==getHash(i+r,j,i+r,j+mid)) {
if (i==2&&j==3) System.out.println(y+" "+(y+mid)+getHash(x+r,y,x+r,y+mid));
if (i==1&&j==3) System.out.println(j+" "+(j+mid)+getHash(i+r,j,i+r,j+mid));
l = mid+1;
} else {
h = mid;
}
}
int c = l;
if (i==1&&j==2) System.out.println(x+" d "+y+" "+r+" "+c);
if (arr[i+r][j+c]>arr[x+r][y+c]) {x = i; y = j;}
}
}
System.out.println(x+" "+y);
for (int i = x;i<x+num;i++) {
for (int j = y;j<y+m;j++) {
if (arr[i][j]==11) io.print("*");
else io.print(".");
}
io.println();
}
io.close();
}
public static long getHash (int i1, int j1, int i2, int j2) {
long sum = prefix[i2][j2];
sum -= (i1==0) ? 0 : prefix[i1-1][j2];
sum -= (j1==0) ? 0 : prefix[i2][j1-1];
sum += (i1==0||j1==0) ? 0 : prefix[i1-1][j1-1];
sum = sum%M; sum = (sum+M)%M;
long inv = (inverse(pow(p,i1))*inverse(pow(q,j1)))%M;
return (sum*inv)%M;
}
public static long[][] hash (int[][] arr) {
long[][] hash = new long[num*2][m*2];
for (int i = 0;i<num*2;i++) {
for (int j = 0;j<m*2;j++) {
long pow = (pow(p,i)*pow(q,j))%M;
hash[i][j] = (arr[i][j]*pow)%M;
}
}
return hash;
}
public static long inverse (long a) { //Returns a/b modulo mod
return pow(a,M-2);
}
public static long pow (long a, long b) {
if (b==0) return 1;
long temp = pow(a,b/2); temp = (temp*temp)%M;
if (b%2==0)
return temp;
else
return (temp*a)%M;
}
public static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
// standard input
public FastIO() { this(System.in, System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) { throw new InputMismatchException(); }
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) { throw new InputMismatchException(); }
if (numChars == -1) {
return -1; // end of file
}
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c;
do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = nextByte();
} while (c > ' ');
return res.toString();
}
public int nextInt() { // nextLong() would be implemented similarly
int c;
do { c = nextByte(); } while (c <= ' ');
int sgn = 1;
if (c == '-') {
sgn = -1;
c = nextByte();
}
int res = 0;
do {
if (c < '0' || c > '9') { throw new InputMismatchException(); }
res = 10 * res + c - '0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}
}
Compilation message
Main.java:34: error: illegal start of expression
long[] rowHash = new long[num*2]; rowHash[0] = getHash(0,)
^
Main.java:34: error: ';' expected
long[] rowHash = new long[num*2]; rowHash[0] = getHash(0,)
^
2 errors
