Problem: Smart Beaver became interested in drawing. He draws suns. However, at some point, Smart Beaver realized that simply drawing suns is boring. So he decided to design a program that will process his drawings. You are given a picture drawn by the beaver. It will have two colors: one for the background and one for the suns in the image. Your task will be to count the number of suns in the image and for each of them to count the number of rays.

Sun is arbitrarily rotated ellipse with rays. Ray is a segment which connects point on boundary of the ellipse with some point outside ellipse.

<image> An image where all suns are circles.  <image> An image where all suns are ellipses, their axes are parallel to the coordinate axes.  <image> An image where all suns are rotated ellipses. 

It is guaranteed that: 

  * No two suns have common points. 
  * The rays’ width is 3 pixels. 
  * The lengths of the ellipsis suns’ axes will lie between 40 and 200 pixels. 
  * No two rays intersect. 
  * The lengths of all rays will lie between 10 and 30 pixels. 

Input

The first line contains two integers h and w — the height and width of the image (1 ≤ h, w ≤ 1600). Next h lines will contain w space-separated integers each. They describe Smart Beaver’s picture. Each number equals either a 0 (the image background), or a 1 (the sun color).

The input limits for scoring 30 points are (subproblem F1): 

  * All suns on the image are circles. 



The input limits for scoring 70 points are (subproblems F1+F2): 

  * All suns on the image are ellipses with axes parallel to the coordinate axes. 



The input limits for scoring 100 points are (subproblems F1+F2+F3):

  * All suns on the image are ellipses, they can be arbitrarily rotated. 

Output

The first line must contain a single number k — the number of suns on the beaver’s image. The second line must contain exactly k space-separated integers, corresponding to the number of rays on each sun. The numbers of the second line must be sorted in the increasing order.

Examples

Note

For each complexity level you are suggested a sample in the initial data. You can download the samples at http://www.abbyy.ru/sun.zip.

Solution (in JAVA):

Solution:
import java.io.PrintStream;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.LinkedList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Abrackadabra
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskF1 solver = new TaskF1();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskF1 extends AbstractChelperSolution {
    String path = "/home/abra/temp/abbyy/sun/package/01.in.txt";
    int width, height;
    int[][] a;
    int[][] directions = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0}
    };
    Set<List<Integer>> areas = new HashSet<List<Integer>>();
    boolean alr = false;
    List<Integer> ans = new ArrayList<Integer>();

    public void solve(int testNumber) {
        if (localMachine) {
            in = new InputReader(path);
        }

        height = in.nextInt();
        width = in.nextInt();

        a = new int[width][height];

        boolean[][] visited = new boolean[width][height];

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                a[j][i] = in.nextInt();
            }
        }

        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (a[i][j] == 0 || visited[i][j]) {
                    continue;
                }

                Queue<Integer> queue = new LinkedList<Integer>();
                queue.add(j * width + i);

                List<Integer> points = new ArrayList<Integer>();

                while (!queue.isEmpty()) {
                    int t = queue.poll();
                    points.add(t);

                    int x = t % width;
                    int y = t / width;

                    for (int[] direction : directions) {
                        int xx = x + direction[0];
                        int yy = y + direction[1];

                        if (xx < 0 || xx >= width || yy < 0 || yy >= height || visited[xx][yy] || a[xx][yy] == 0) {
                            continue;
                        }

                        visited[xx][yy] = true;
                        queue.add(xx + yy * width);
                    }
                }

                areas.add(points);
            }
        }

        for (List<Integer> area : areas) {
            double mx = 0.0;
            double my = 0.0;
            int tot = 0;

            for (int p : area) {
                int i = p % width;
                int j = p / width;
                int total = 0;
                int good = 0;

                for (int x = i - 3; x <= i + 3; x++) {
                    for (int y = j - 3; y <= j + 3; y++) {
                        if (x < 0 || x >= width || y < 0 || y >= height) {
                            continue;
                        }
                        total++;
                        if (a[x][y] != 0) {
                            good++;
                        }
                    }
                }

                if (1.0 * good / total > 0.95) {
                    a[i][j] = 2;
                    tot++;
                    mx += i;
                    my += j;
                }
            }

            mx /= tot;
            my /= tot;

            int tries = 2500;

            boolean[] r = new boolean[tries];
            int[][] coords = new int[tries][2];

            for (int i = 0; i < tries; i++) {
                double ang = Math.PI * 2 * i / tries;
                for (int t = 0; true; t++) {
                    int x = (int) Math.round(mx + t * Math.cos(ang));
                    int y = (int) Math.round(my + t * Math.sin(ang));
                    if (x < 0 || x >= width || y < 0 || y >= height || a[x][y] == 0) {
                        boolean ok = false;
                        int total = 0;
                        int good = 0;

                        for (int xx = x - 5; xx <= x + 5; xx++) {
                            for (int yy = y - 5; yy <= y + 5; yy++) {
                                if (xx < 0 || xx >= width || yy < 0 || yy >= height) {
                                    continue;
                                }
                                total++;
                                if (a[xx][yy] != 0) {
                                    good++;
                                }
                            }
                        }

                        if (1.0 * good / total < 0.24) {
                            ok = true;
                        }

                        r[i] = ok;
                        coords[i][0] = x;
                        coords[i][1] = y;

                        break;
                    }
                }
            }

            int rays = 0;

            for (int i = 0; i < tries; i++) {
                if (!r[i]) {
                    continue;
                }

                int t = i;

                while (r[(t - 1 + tries) % tries]) {
                    t = (t - 1 + tries) % tries;
                }

                while (r[t]) {
                    r[t] = false;
                    t = (t + 1) % tries;
                }

                rays++;
            }

            if (!alr) {
                ans.add(rays);
            }
        }
        Collections.sort(ans);
        if (!alr) {
            out.println(ans.size());
            for (int i : ans) {
                out.print(i + " ");
            }
        }
        alr = true;
    }
}

abstract class AbstractChelperSolution {
    protected InputReader in;
    protected OutputWriter out;
    protected OutputWriter log;
    //protected boolean localMachine = System.getenv().containsKey("USER") && System.getenv("USER").equals("abra");
    protected boolean localMachine = Package.getPackage("chelper") != null;

    {
        if (localMachine) {
            log = new OutputWriter(new OutputStream() {
                @Override
                public void write(int b) throws IOException {
                    System.err.write(b);
                }
            });
        } else {
            log = new OutputWriter(new OutputStream() {
                @Override
                public void write(int b) throws IOException {
                }
            });
        }
    }

    public void solve(int testNumber, InputReader in, OutputWriter out) {
        this.in = in;
        this.out = out;

        if (testNumber == 1) {
            precalc();
        }
        testStarts(testNumber);

        solve(testNumber);

        testEnds(testNumber);
        log.flush();
    }

    public abstract void solve(int testNumber);

    public void testStarts(int testNumber) {}

    public void testEnds(int testNumber) {}

    public void precalc() {}
}

class InputReader implements Iterable<String> {
    BufferedReader br;
    StringTokenizer in;

    public InputReader(String fileName) {
        try {
            br = new BufferedReader(new FileReader(fileName));
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public InputReader(InputStream inputStream) {
        br = new BufferedReader(new InputStreamReader(inputStream));
    }

    String lastLine = null;

    boolean hasMoreTokens() {
        while (in == null || !in.hasMoreTokens()) {
            lastLine = nextLine();
            if (lastLine == null) {
                return false;
            }
            in = new StringTokenizer(lastLine);
        }
        return true;
    }

    public String nextString() {
        return hasMoreTokens() ? in.nextToken() : null;
    }

    public String nextLine() {
        boolean somethingLeft = in != null && in.hasMoreTokens();
        in = null;
        if (somethingLeft) {
            return lastLine;
        }
        try {
            return br.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public Iterator<String> iterator() {
        return new Iterator<String>() {
            @Override
            public boolean hasNext() {
                return hasMoreTokens();
            }

            @Override
            public String next() {
                return nextString();
            }

            @Override
            public void remove() {
                throw new RuntimeException();
            }
        };
    }
}

class OutputWriter extends PrintWriter {

    public OutputWriter(String fileName) {
        super(createFileWriter(fileName));
    }

    private static Writer createFileWriter(String s) {
        Writer writer;

        try {
            writer = new FileWriter(s);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }

        return writer;
    }

    public OutputWriter(OutputStream outputStream) {
        super(outputStream);
    }

    public OutputWriter(Writer writer) {
        super(writer);
    }

    }