Printing characters in a matrix as a string

I need to solve this problem in Python 3 (within 3 sec):


A is a given (NxM) rectangle, filled with characters "a" to "z".
Start from A[1][1] to A[N][M] collect all character which is only
one in its row and column, print them as a string.


Input:


\$N\$, \$M\$ in first line (number of row and column \$1 \le N\$, \$M \le
> 1000\$). Next, \$N\$ lines contain exactly \$M\$ characters.


Output:

A single string



Sample input 1:

1 9
arigatodl



Sample output 1:

rigtodl



Sample input 2:

5 6
cabboa
kiltik
rdetra
kelrek
dmcdnc



Sample output 2:

codermn


This is still not fast enough when \$N\$, \$M\$ = 1000. I'd like suggestions on improving the speed, or any other ways to solve the given problem, as long as the solution is in Python 3 and is faster than mine.

from operator import itemgetter
Words,Chars,answer=[],"abcdefghijklmnopqrstuvwxyz",""
N,M=[int(i) for i in input().split()]
for _ in range(N):
Words.append(input())
# got the inputs
for row,word in enumerate(Words): # going through each words
Doubts=[] # collect chars only one in its row.
for char in Chars:
if (word.count(char)==1):
Doubts.append((char,word.index(char)))
for case in sorted(Doubts,key=itemgetter(1)): #sorting by index
doubtless=True #checking whether 1 in its column or not.
for i in range(N):
if (Words[i][case[1]]==case[0] and i!=row):
doubtless=False
break
if (doubtless):
answer+=case[0] #if char is one in its row and column, adds to answer.
print (answer)


I would suggest to create a 1000x1000 testcase and measure the performance before the optimization process. Please use the following test generator:

import os
import random

f = open('1000x1000.in','w')
f.write('1000 1000\n')
ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(1000):
       f.write(''.join([ALPHABET[random.randint(0, len(ALPHABET)-1)] for _ in range(1000)]) + '\n')
f.close()

After that just run it and measure the performance of your application. I got about 47 ms on my pretty old C2D E7200.

StackExchange Code Review Q#14766, answer score: 2