/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		final String regex = "(?:\\b(?:dog|cat)s?|\\G)\\s+(?:((?!(?:dog|cat)s?\\b)\\w{3,})|\\S+)(?=.*?\\s+(?:dog|cat)s?\\b)";
		final String string = "Dogs are nice animals. Cats are not. My cat ate a mice. My dog once ate a fry. My dog once ate a fry. My cat ate a mice. The catalog of the best dogs is around here somewhere.";
 
		final Pattern pattern = Pattern.compile(regex, Pattern.MULTILINE | Pattern.CASE_INSENSITIVE);
		final Matcher matcher = pattern.matcher(string);
 
		while (matcher.find()) {
		    for (int i = 1; i <= matcher.groupCount(); i++) {
		    	if (matcher.group(i) != null)
		        	System.out.println( matcher.group(i));
		    }
		}
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLnV0aWwucmVnZXguTWF0Y2hlcjsKaW1wb3J0IGphdmEudXRpbC5yZWdleC5QYXR0ZXJuOwoKLyogTmFtZSBvZiB0aGUgY2xhc3MgaGFzIHRvIGJlICJNYWluIiBvbmx5IGlmIHRoZSBjbGFzcyBpcyBwdWJsaWMuICovCmNsYXNzIElkZW9uZQp7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlmaW5hbCBTdHJpbmcgcmVnZXggPSAiKD86XFxiKD86ZG9nfGNhdClzP3xcXEcpXFxzKyg/OigoPyEoPzpkb2d8Y2F0KXM/XFxiKVxcd3szLH0pfFxcUyspKD89Lio/XFxzKyg/OmRvZ3xjYXQpcz9cXGIpIjsKCQlmaW5hbCBTdHJpbmcgc3RyaW5nID0gIkRvZ3MgYXJlIG5pY2UgYW5pbWFscy4gQ2F0cyBhcmUgbm90LiBNeSBjYXQgYXRlIGEgbWljZS4gTXkgZG9nIG9uY2UgYXRlIGEgZnJ5LiBNeSBkb2cgb25jZSBhdGUgYSBmcnkuIE15IGNhdCBhdGUgYSBtaWNlLiBUaGUgY2F0YWxvZyBvZiB0aGUgYmVzdCBkb2dzIGlzIGFyb3VuZCBoZXJlIHNvbWV3aGVyZS4iOwoJCQoJCWZpbmFsIFBhdHRlcm4gcGF0dGVybiA9IFBhdHRlcm4uY29tcGlsZShyZWdleCwgUGF0dGVybi5NVUxUSUxJTkUgfCBQYXR0ZXJuLkNBU0VfSU5TRU5TSVRJVkUpOwoJCWZpbmFsIE1hdGNoZXIgbWF0Y2hlciA9IHBhdHRlcm4ubWF0Y2hlcihzdHJpbmcpOwoJCQoJCXdoaWxlIChtYXRjaGVyLmZpbmQoKSkgewoJCSAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtYXRjaGVyLmdyb3VwQ291bnQoKTsgaSsrKSB7CgkJICAgIAlpZiAobWF0Y2hlci5ncm91cChpKSAhPSBudWxsKQoJCSAgICAgICAgCVN5c3RlbS5vdXQucHJpbnRsbiggbWF0Y2hlci5ncm91cChpKSk7CgkJICAgIH0KCQl9Cgl9Cn0=