#include <bits/stdc++.h>                                                                         
                                                                                                 
using namespace std;                                                                             
                                                                                                 
#define all(x) x.begin(), x.end()                                                                
#define rep(i, n) for (int i = 0; i < n; ++i)                                                    
#define reps(i, m, n) for (int i = m; i <= n; ++i)                                               
                                                                                                 
using i64 = long long;                                                                           
using pii = pair<i64, i64>;                                                                      
                                                                                                 
template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}       
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}       
                                                                                                 
constexpr int INF = 0x3f3f3f3f;                                                                  
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;                                                       
constexpr int MOD = int(1e9) + 7;                                                                
                                                                                                 
i64 lcm(i64 a, i64 b) { return a / __gcd(a, b) * b; }                                            
                                                                                                 
signed main()                                                                                    
{                                                                                                
  ios::sync_with_stdio(false);                                                                   
  cin.tie(nullptr);                                                                              
                                                                                                 
  i64 n, m;                                                                                      
  cin >> n >> m;                                                                                 
                                                                                                 
  i64 l = lcm(n, m);                                                                             
                                                                                                 
  string s, t;                                                                                   
  cin >> s >> t;                                                                                 
                                                                                                 
  map<i64, i64> mp;                                                                              
  for (i64 i = 0; i < n; ++i) {                                                                  
    mp[i*(l/n)+1] = s[i];                                                                        
  }                                                                                              
                                                                                                 
  for (i64 i = 0; i < m; ++i) {                                                                  
    i64 tmp = mp[i*(l/m)+1];                                                                     
    if (tmp != t[i] && tmp != 0) {                                                               
      cout << -1 << "\n";                                                                        
      return 0;                                                                                  
    }                                                                                            
  }                                                                                              
                                                                                                 
  cout << l << "\n";                                                                             
                                                                                                 
  return 0;                                                                                      
}                                                                                                

Measured memory_bytes: 10880