- /* in the name of Anton */
-
- /*
- Compete against Yourself.
- Author - Aryan (@aryanc403)
- Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
- */
-
- #ifdef ARYANC403
- #include <header.h>
- #else
- #pragma GCC optimize ("Ofast")
- #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
- //#pragma GCC optimize ("-ffloat-store")
- #include<bits/stdc++.h>
- #define dbg(args...) 42;
- #endif
-
- // y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
- // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
- template<class Fun> class y_combinator_result {
- Fun fun_;
- public:
- template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
- template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
- };
- template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
-
- using namespace std;
- #define fo(i,n) for(i=0;i<(n);++i)
- #define repA(i,j,n) for(i=(j);i<=(n);++i)
- #define repD(i,j,n) for(i=(j);i>=(n);--i)
- #define all(x) begin(x), end(x)
- #define sz(x) ((lli)(x).size())
- #define pb push_back
- #define mp make_pair
- #define X first
- #define Y second
- #define endl "\n"
-
- typedef long long int lli;
- typedef long double mytype;
- typedef pair<lli,lli> ii;
- typedef vector<ii> vii;
- typedef vector<lli> vi;
-
- const auto start_time = std::chrono::high_resolution_clock::now();
- void aryanc403()
- {
- #ifdef ARYANC403
- auto end_time = std::chrono::high_resolution_clock::now();
- std::chrono::duration<double> diff = end_time-start_time;
- cerr<<"Time Taken : "<<diff.count()<<"\n";
- #endif
- }
-
- long long readInt(long long l, long long r, char endd) {
- long long x=0;
- int cnt=0;
- int fi=-1;
- bool is_neg=false;
- while(true) {
- char g=getchar();
- if(g=='-') {
- assert(fi==-1);
- is_neg=true;
- continue;
- }
- if('0'<=g&&g<='9') {
- x*=10;
- x+=g-'0';
- if(cnt==0) {
- fi=g-'0';
- }
- cnt++;
- assert(fi!=0 || cnt==1);
- assert(fi!=0 || is_neg==false);
-
- assert(!(cnt>19 || ( cnt==19 && fi>1) ));
- } else if(g==endd) {
- if(is_neg) {
- x=-x;
- }
- assert(l<=x&&x<=r);
- return x;
- } else {
- assert(false);
- }
- }
- }
- string readString(int l, int r, char endd) {
- string ret="";
- int cnt=0;
- while(true) {
- char g=getchar();
- assert(g!=-1);
- if(g==endd) {
- break;
- }
- cnt++;
- ret+=g;
- }
- assert(l<=cnt&&cnt<=r);
- return ret;
- }
- long long readIntSp(long long l, long long r) {
- return readInt(l,r,' ');
- }
- long long readIntLn(long long l, long long r) {
- return readInt(l,r,'\n');
- }
- string readStringLn(int l, int r) {
- return readString(l,r,'\n');
- }
- string readStringSp(int l, int r) {
- return readString(l,r,' ');
- }
-
- void readEOF(){
- assert(getchar()==EOF);
- }
-
- vi readVectorInt(int n,lli l,lli r){
- vi a(n);
- for(int i=0;i<n-1;++i)
- a[i]=readIntSp(l,r);
- a[n-1]=readIntLn(l,r);
- return a;
- }
-
- bool isBinaryString(const string s){
- for(auto x:s){
- if('0'<=x&&x<='1')
- continue;
- return false;
- }
- return true;
- }
-
- // #include<atcoder/dsu>
- // vector<vi> readTree(const int n){
- // vector<vi> e(n);
- // atcoder::dsu d(n);
- // for(lli i=1;i<n;++i){
- // const lli u=readIntSp(1,n)-1;
- // const lli v=readIntLn(1,n)-1;
- // e[u].pb(v);
- // e[v].pb(u);
- // d.merge(u,v);
- // }
- // assert(d.size(0)==n);
- // return e;
- // }
-
- const lli INF = 0xFFFFFFFFFFFFFFFL;
-
- lli seed;
- mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
- inline lli rnd(lli l=0,lli r=INF)
- {return uniform_int_distribution<lli>(l,r)(rng);}
-
- class CMP
- {public:
- bool operator()(ii a , ii b) //For min priority_queue .
- { return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
-
- void add( map<lli,lli> &m, lli x,lli cnt=1)
- {
- auto jt=m.find(x);
- if(jt==m.end()) m.insert({x,cnt});
- else jt->Y+=cnt;
- }
-
- void del( map<lli,lli> &m, lli x,lli cnt=1)
- {
- auto jt=m.find(x);
- if(jt->Y<=cnt) m.erase(jt);
- else jt->Y-=cnt;
- }
-
- bool cmp(const ii &a,const ii &b)
- {
- return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
- }
-
- const lli mod = 1000000007L;
- // const lli maxN = 1000000007L;
-
- lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
- lli m;
- string s;
- vi a;
- //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
-
- int main(void) {
- ios_base::sync_with_stdio(false);cin.tie(NULL);
- // freopen("txt.in", "r", stdin);
- // freopen("txt.out", "w", stdout);
- // cout<<std::fixed<<std::setprecision(35);
- T=readIntLn(1,1e3);
- lli sumNM = 4e5;
- const vii dir={{0,1},{1,0}};
- while(T--)
- {
- const lli n = readIntSp(2,1e5);
- const lli m = readIntSp(2,1e5);
- sumNM-=n*m;
- assert(sumNM>=0);
- const lli k = readIntLn(1,1e9);
- vector<string> a(n);
- for(auto &s:a){
- s=readStringLn(m,m);
- assert(isBinaryString(s));
- }
-
- auto runBulk=[&](lli k)->void{
- if(k==0)
- return;
- vector<vi> b(n,vi(m));
- b[0][0]=k;
- for(lli sum=0;sum<n+m;++sum){
- for(lli i=max(0LL,sum-m);i<n&&i<=sum;++i){
- const lli j=sum-i;
- if(j<0||j>=m||b[i][j]==0)
- continue;
- if(i==n-1||j==m-1){
- if(i==n-1&&j==m-1)
- continue;
- if(i==n-1){
- if(a[i][j]=='0'){
- b[i][j+1]++;
- a[i][j]^=1;
- }
- continue;
- }
-
- if(j==m-1){
- if(a[i][j]=='1'){
- b[i+1][j]++;
- a[i][j]^=1;
- }
- continue;
- }
- assert(false);
- }
- const lli c=b[i][j];
- b[i+1][j]+=c/2;
- b[i][j+1]+=c/2;
- if(c%2==0)
- continue;
- const auto d=dir[a[i][j]-'0'];
- a[i][j]^=1;
- b[i+d.X][j+d.Y]++;
- }
- }
- };
-
- auto runOnce=[&]()->ii{
- dbg(a);
- lli i=0,j=0;
- while(i<n&&j<m){
- const auto d=dir[a[i][j]-'0'];
- if(i+d.X>=n||j+d.Y>=m)
- return {i,j};
- a[i][j]^=1;
- i+=d.X;
- j+=d.Y;
- }
- assert(false);
- };
-
- runBulk(k-1);
- ii ans=runOnce();
- cout<<ans.X+1<<" "<<ans.Y+1<<endl;
-
- } aryanc403();
- readEOF();
- return 0;
- }